Unique number - ii doubt

#1

#include
int main() {

int n;
cin >> n;

int a[n];
for (int i = 0; i < n; i++) {
    cin >> a[i];
}

int mask=0;
for (int i = 0; i < n; i++) {
    mask^=a[i];
}
int result=mask;
int count=0;
if(!(mask&1)){   // I AM HAVING  PROBLEM HERE UNDERSTANDING THIS LOOP WHAT IT DOES IF PROGRAM GO INSIDE THIS LOOP IN BHAIYA'S EXAMPLE THE PROGRAM DIDNT GO SO IT SATISIFIED COUNT ZERO CAN  ANYONE TELL
    count++;
    mask>>=1;
}
mask = 1;
while(count--){
    mask<<=1;
}

int num1 =0;
int num2 = 0;
for (int i = 0; i < n; i++) {
    if((a[i]&mask)!=0){
        num1^=a[i];
    }
}
num2=result^num1;

if(num1<num2){
    cout << num1<<" "<<num2 <<endl;
}else{
    cout << num2<<" "<<num1 <<endl; 
}

return 0;

}

// I AM HAVING PROBLEM HERE UNDERSTANDING LOOP(SEE CODE) WHAT IT DOES IF PROGRAM GO INSIDE THE LOOP IN BHAIYA’S EXAMPLE THE PROGRAM DIDNT GO SO IT SATISIFIED COUNT ZERO CAN ANYONE TELL WHEN THEIR IS COUNT++

#2 
while(!(mask&1)){
    count++;
    mask>>=1;
}

It’ll find the position of first set bit in mask(right shift while mask&1 is 0). Now the first set bit(1) will tell us that one of the two unique numbers had 1 in that position(since, 0^1=1^0=1). Now we initialise mask with 1 and left shift it that many times(count) to generate a number that has 1 in the exact same position and finally pick the element which’ll have a[i]&mask non-zero.
e.g. if n=6 and arr is 1 12 2 8 1 2, result will hold initial mask i.e. 12^8=4. So when it goes to the while((!(mask&1)) loop, count will be 2 and then the second loop while(count--) will make it 4
(binary - 100).

1 Like