0

Basically, I was wondering if one can find whether there are any (or at a least) a single duplicate in a set of numbers (eg: 2,7,3,7,6,5,4 => 7).

flag
2 
 I don't think this question belongs on MO -- see mathoverflow.net/faq#whatquestions -- or otherwise it's unclear what you're looking for. – Max Feb 14 2011 at 9:15
3 
 en.wikipedia.org/wiki/… – Boris Bukh Feb 14 2011 at 9:16
This is not at all my subject, but anyway - this is a standard computer science question; there is an obvious (and slow) algorithm - check all possible pairs of numbers for equality, which is $O(n^2)$ for $n$ elements. If you can find a reasonably easy hashing function, then a hash table lookup method would be much faster in practice (but that assumes you know the type of elements under consideration, in this case just numbers). However, for general sets with no restriction on the type of elements, I expect it would be hard (or maybe impossible?!) to improve much on the obvious algorithm. – Zen Harper Feb 14 2011 at 9:17
...having just looked at the wikipedia link, supplied by Boris Bukh, I see that my beginner's comment is rather unnecessary! – Zen Harper Feb 14 2011 at 9:20
I must admit the question came from a CS background, but as my question clearly said, I was asking for a purely mathematical approach to the problem. I think that wiki article pretty much answers my question. – profilesuuf6429 Feb 14 2011 at 9:31
show 1 more comment

closed as off topic by Angelo, Zev Chonoles, Andrey Rekalo, J.C. Ottem, S. Carnahan♦ Feb 14 2011 at 9:26

Browse other questions tagged or ask your own question.