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

Question

How to find duplicates in an array. In the case of the inverse problem, when you need to find a unique element from all, it is clear that you are just xor all the elements, and as a result we get a unique element. For instance,

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 for an array

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

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

Answer 1

You describe Element Distinctness Problem .

Without extra space (and hashing), there is no O(n) solution for the element clarity problem, so you cannot change the “xor algorithm for duplicate” for this problem.

Solutions for this task:

• sort and iterate over the sorted array to find duplicates (easily sorted array). This is O(nlogn) .
• Create a histogram of the data (based on the hash) and iterate over the histogram when done to check if all elements have a value of 1 in the histogram - O(n) middle case, O (n) space.

Answer 2

We can find duplicates in the array 0 (n) times using the following algorithm.

  traverse the list for i= 0 to n-1 elements { //check for sign of A[abs(A[i])] ; if positive then make it negative by A[abs(A[i])]=-A[abs(A[i])]; else // ie, A[abs(A[i])] is negative this element (ith element of list) is a repetition } 

Hope this helps!

Answer 3

One solution might be to build a hashset. This happens as follows:

  1. Initialize an empty hashset. 2. For each element in array, a. Check if it is present in the hashset. If yes, you found the duplicate If not, add it to the hashset. 

This way you can find all duplicates in the array.

The complexity of the space: O (n); Difficulty of time: O (n)