Find duplicates in an array, without using any extra space

Question

Given an array of n integer elements how will you find whether there are duplicates in the array in O(n) time without using any extra space.

With extra space it means extra space of order O(n).

Does the Xor operator help in any way.

Answer 1

If there is no additional information, this question seems to be unsolveable, as this is the Element Distinctness Problem, which is unsolveable with the restrictions you provided, in the required time.

you can allow:

(1) more memory and use a hashtable / hashset and meet the O(n) time criteria. [iterate the array, check if an element is in the hash table, if it is you have dupes, otherwise - insert the element into the table and continue].

(2) more time, sort the array [O(nlogn)] and meet the sub-linear space criteria. [After sorting, iterate over the array, and for each a[i] , a[i+1] , check if they are identical. If you did not find an identical pair, you have no dupes]

EDIT: The proof for this claim is a bit lengthy, and needs mathematical notation that are not supported here (sidenote: we really need tex support), but the idea is if we model our problem as an Algebraic Computation Tree (which is a fair assumption when no hashing is allowed, and constant space at out disposal), then, Ben Or proved in his article Lower Bounds For Algebraic Computation Trees (1983) (published in prestiged ACM), that element distinctness is Omega(nlogn) problem under this model. Lubiw showed that the same conclusion also applies when limiting ourselves to integers in 1991: A Lower Bound for the Integer Element Distinctness Problem, but these articles conclude that under the algebraic tree computation model - Integer Distinctness Problem is Omega(nlogn) Problem.