How to find duplicates in the array for xor method? algorithm complexity O(n)

Question

How to find duplicates in the array. In the case of the inverse problem when you have to find a unique element of all is clear you just xor all the elements and as a result we obtain a unique element.For example

int a[] = {2, 2, 3, 3, 4, 5, 5, 16, 16};
int res = a[0];
for(int i = 0; i < 9; ++i)
    res ^= a[i];

for example given an array

int a[] = {2, 4, 7, 8, 4, 5};

Here a duplicate is 4, but it is not clear how to find a duplicate element of the array.

Answer 1

You are describing the Element Distinctness Problem.

Without extra space (and hashing) there is no O(n) solution to element distinctness problem, so you cannot modify the "xor algorithm for duplicate" for this problem.

The solutions for this problem are:

1. sort and iterate the sorted array to find dupes (easy in sorted array). This is O(nlogn) time.
2. Build a histogram of the data (hash-based) and iterate the histogram when done to verify if all elements have value of 1 in the histogram - O(n) average case, O(n) space.