Q:

# C++ program to find Unique Number using Bit Masking

C++ Program to find unique number in an array of n numbers in which except one (unique number) rest all are present thrice.

Constraints: n<10^5

Example:

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

Output:
4
```

Solution: Except 4 rest all have multiplicity of 3 in array. For instance 4 are represented as 100 in binary .Starting from left most bit is the first index of count array.

need an explanation for this answer? contact us directly to get an explanation for this answer

Program:

``````#include <iostream>
using namespace std;

int unique(int *arr,int n)
{
//array of size 64 for max 64 bit size
int count[64]={0};

//count array stores bit of every number
for(int k=0;k<n;k++)
{
int i=0;
int num=arr[k];
while(num>0)
{
// extract bit
count[i]+=(num&1);
i++;
// right shift to get next leftmost bit
num=num>>1;
}
}

// starting from first index 2^0=1
int power=1;
int result=0;
for(int j=0;j<64;j++)
{
// take modulus of count array by 3
count[j] %=3;
result+=count[j]*power;
// binary to decimal operation
power=power<<1;
}
// if there is no unique number 0 is returned
return result;
}

int main()
{
int arr[50];
int n;
cout<<"Enter lenght of the array: ";
cin>>n;

cout<<"Enter array elements..."<<endl;
for(int c=0;c<n;c++)
{
cin>>arr[c];
}
cout<<unique(arr,n)<<" is the unique number in array.";

return 0;
}
``````

Output

```Enter lenght of the array: 4
Enter array elements...
10 10 10 40
40 is the unique number in array.```

need an explanation for this answer? contact us directly to get an explanation for this answer