-
Notifications
You must be signed in to change notification settings - Fork 253
/
Unique number 3.cpp
51 lines (44 loc) · 1.04 KB
/
Unique number 3.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*We are given an array containg n numbers. All the numbers are present thrice except for one number which is only present once.
Find the unique number. Only use - bitwise operators, and no extra space.
Input Format
First line contains the number n. Second line contains n space separated number.
Constraints
N < 10^5
Output Format
Output a single line containing the unique number
Sample Input
7
1 1 1 2 2 2 3
Sample Output
3
Explanation
3 is present only once*/
#include<iostream>
using namespace std;
int main(){
int n,no;
int cnt[64]={0}; //maximum we can have 64 bits
cin>>n;
for(int i=0;i<n;i++){
cin>>no;
//update the cnt array by extracting bits
int j=0;
while(no>0){
int last_bit=(no&1);
cnt[j]+=last_bit;
j++;
no=no>>1;
}
}
//iterate over the array and form the answer by converting binary to decimal number
int p=1;
int ans=0;
for(int i=0;i<64;i++){
cnt[i]%=3;
ans+=(cnt[i]*p);
p=p<<1;
}
//print the final answer
cout<<ans<<endl;
return 0;
}