Q:

# C++ program to find two unique numbers in an array

Write a C++ program that accepts input array from user and find the two unique number which occurred only once in array.

Example:

```    Input:
10
1 1 2 3 3 4 4 5 6 6

Output:
2 5
```

Explanation:

This problem can be solved using the concept of Bitwise XOR, Bitwise AND, and bit masking.

Bitwise XOR:

Bitwise XOR ( ^ ) takes two equal-length bit patterns. If both bits in the compared position of the bit patterns are 0 or 1, the bit in the resulting bit pattern is 0, otherwise 1.

Example:

```    A = 5 = 0101, B = 3 = 0011
A ^ B = 0101 ^ 0011 = 0110 = 6

Special Property of XOR:
A^A =0
A^0 = A
```

Bitwise AND

Bitwise AND ( ^ ) takes two equal-length bit patterns. The output of bitwise AND is 1 if the corresponding bits of two operands is 1. If either bit of an operand is 0, the result of corresponding bit is evaluated to 0.

Example:

```    A = 5 = 0101, B = 3 = 0011
A & B = 0101 & 0011 = 0001 = 1
```

For the current problem:

1. First we take XOR of all elements of array.
2. Suppose we have: 1,1,2,3,3,4,4,5,6,6
3. On taking XOR of all elements, this will remove duplicates elements as A ^A =0
Then we get: 2^5 from above result
4. The result of 2^5 will definitely have at least a set bit, to find the rightmost set bit we do res&1 and make a count to take the record of current position. If we get a non-zero res&1 that's the position we want to get, break the loop, otherwise right shift the res and increment the count.
5. Make a mask using 1<<count, and take & one by one with all elements, Elements resulting a non zero result of mask &arr[i], take XOR of them .
6. Resulting XOR will result in firstNo.
7. Now for SecondNo, take XOR of firstNo with initial res. i.e., firstNo^ firstNo ^ secondNo.
8.

Program:

``````#include<bits/stdc++.h>
using namespace std;

int findRightMostBit(int x) {
int i = 0;
while (x > 0) {
if(x&1){
return i;
}
x>>1;
i++;
}
return i;
}

void findUnique(int arr[], int size) {
int res = 0;
for (int i = 0; i < size; ++i) {
res = res ^ arr[i];
}

int bitPos = findRightMostBit(res);
int mask = (1 << bitPos);
int firstNo=0;
for (int i = 0; i < size; ++i)
{
if ((mask & arr[i]) != 0) {
firstNo = firstNo ^ arr[i];
}
}
int secondNo = firstNo^ res;
cout<<"Two Unique Numbers : "<<firstNo<<" , "<<secondNo;
}

int main() {
int n;

cout<<"Enter size of array : ";
cin>>n;

int arr[n];

cout<<"Enter elements of array : \n";
for (int i = 0; i < n; ++i)
{
cin>>arr[i];
}

findUnique(arr, n);

return 0;
}``````

Output

```Enter size of array : 10
Enter elements of array :
1 1 2 3 3 4 4 5 6 6
Two Unique Numbers : 5 , 2
```