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

C++ program to find two unique numbers in an array: Here, we are going to learn how to find two unique numbers in a given array using bitwise operators?
Submitted by Bhanu Pratap Raghav, on December 24, 2018

Description:

Solution to find the two unique numbers from the set of numbers which occurred twice accept the unique numbers

Problem statement:

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.

Algorithm:

1. Set res=0 and find its XOR with all other elements of array.
2. Now res = firstNo ^ secondNo.
3. Get rightmost set bit position of res. using function findRightMostBit
4. Set bitPos = position of rightmost set bit.
5. Set a mask with a structure of set bit at position bitPos, using 1<<bitPos.
6. Set firstNo=0
7. ```For i=0 to size of array
If mask & arr[i] != 0
firstNo = firstNo ^ arr[i]
//End of if
//End of loop
```
8. Set secondNo=firstNo ^ res.
9. Print firstNo and secondNo.

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
```

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates