### Duplicate XOR Array Problem | Bitmasking

**Problem:** Given an list of array. Find the elements which is occurring one time.

Input:- { 3, 4, 7, 8, 4, 3, 1, 2, 1, 2} Output:- 7 8

Time complexity:- O(n)

Space complexity:- O(1).

Solution:-

As we know the XOR of same element gives 0 , unless it gives 1.

X ^ 1=X X ^ X=0

So, If we calculate the XOR of elements, which are occurring twice , then they will get cancel with each other and we will be left with the XOR of Distinct Elements.

Now, we are left with the Two distinct elements , to which their XOR can never be zero because only XOR of elements with itself is zero.

So, the overall result will never ne zero if there are 2 distinct elements in the array.

Therefore , the result will have some ‘K’ bit which is set in either of the two distinct element.(say x and y) Result= x^ y We will now pick any “k” set bit from the result and store its index. And will now split the original array into two parts.

Step to find the two distinct elements:-

1:- First half will consists of those elements whose “k” bit is set (i.e 1).

2:- Second half will consists of elements where “k” bit is turned off.

3:- Now run a loop, and 3.1 Perform AND operation with mask and element of array. If it gives 1, that means the element consists a set bit in same position as in the result. 3.2 For the second number , XOR it with Result and First number , you will get the second distinct number.

Code:-

#include<iostream> using namespace std; void unique_number(int ar[], int n) { int result=0; int i=0; for(i=0;i<n;i++) result^=ar[i]; //XOR of all elements int temp=result; //storing result in temp int j=0; while(temp) { if(temp&1) //finding the set bit break; } j++; int mask=(1<<j); //making mask value equal to 'k' bit int first_no=0; for(i=0;i<n;i++) { if(mask&ar[i]) //if set bit of element of array is on i.e 1 first_no^=ar[i]; } int second_no=first_no^result; // Second number by XOR of result and first number cout<<first_no<< ' '<<second_no; } int main() { int n; cin>>n; int ar[n]; for(int i=0;i<n;i++) { cin>>ar[i]; } unique_number(ar, n); //function call return 0; }

CommentsNo comment yet.