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.
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:
O(nlogn) time.O(n) average case, O(n) space.We can find the duplicates in an array in 0(n) time by 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 // i.e., A[abs(A[i])] is negative
this element (ith element of list) is a repetition
}
Hope it helps!
One solution can be to build a Hashset. It goes 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 the duplicates in the array.
Space complexity: O(n) ; Time complexity: O(n)
