O(n^2) is the usual naive answer but there are properties that if true can reduce this to O(n) using bit ops:

In general, if the given array range can also be generated where the duplicated number you are trying to find gets no special treatment and is included just like all the rest a single time, then you can get the answer this way:

set total to 0

foreach (n in given array)

xor all n into total

foreach (n in generated range)

xor all n into total

total is your answer

This works because all the non-duplicated single entries will cancel out via xor with their single entry from the generated set (since they are all paired) and the duplicated number will have an extra odd entry (since it will have 2 entries already from the given array + 1 from the generated set = 3 entries).

And because of course xor is commutative; the order of the xor'ing doesn't matter:

6^6^5^5^4^4 = 0, as does 6^5^4^5^4^6

It is a variation of these problems:

- find a missing number in an unsorted array

- find an unduplicated number in an unsorted array of duplicates

findDuplicates(int array[])

{

int duplicates[] , index;

for (int i=0; ii; j--)

{

if (array[i] == array[j])

{

duplicates[index++] = array[i];

break;

}

}

print duplicates;