Alex Loves Bitmasking - Editorials

Practice :

https://www.codechef.com/problems/CODEPHR1

Contest Page :

https://www.codechef.com/COPR2020/problems/CODEPHR1

Author :

CodeAsylums

Tester :

CodeAsylums

Editorialist :

CodeAsylums

DIFFICULTY:

Simple

PREREQUISITES:
Logic Gates , Hamming Distance

PROBLEM:

Find the value of a given expression Y = (P bitwise OR Q) XOR (P bitwise AND Q) , where P is the sum of those unique elements (a+b) and Q is hamming distance between them.

CONSTRAINTS:

1<=n<=10^6

1<= elements of array <= 10^5

QUICK EXPLANATION:

Find both a and b, for hamming distance calculate set bits in (A^B), and apply the given condition

EXPLANATION:

To find the unique element in an array we XOR all the elements. Here to find two unique elements, we XOR the array and get a^b as the result. Now to segregate the numbers, we take any set bit in (A^B). Now we divide the original array into two parts, one which has that particular set bit, we xor that array and get A(say). Now we XOR A with (A^B) we to get B. Now calculate p=a+b and calulate Q ie the hamming distance of a and b by counting set bits of (A^B). Then simply use the given conditionY = (P bitwise OR Q) XOR (P bitwise AND Q) to compute the final answer.

SOLUTION:

#include<bits/stdc++.h>
using namespace std;
void hamming_unique2(vector arr, int n)
{
int first = 0,second=0;
for(int i=0;i<n;i++)
{
first ^= arr[i];
}
int Q = __builtin_popcount(first); /// hamming distance
int temp = first;
int mask =0,i=0;
while(temp>0)
{
if(temp&1)
{
mask = 1<<i;
break;
}
temp >>= 1;
i++;
}
for(int i=0;i<n;i++)
{
if(mask&arr[i])
{
second ^= arr[i];
}
}
first ^=second;
int P= first+second; ///sum
int Y = (P|Q)^(P&Q); ///value of expression
cout<<Y;
}
int main()
{
int n;
cin>>n;
vector arr(n,0);
for(int i=0;i<n;i++)
{
int num;
cin>>num;
arr[i] = num;

}
hamming_unique2(arr,n);
return 0;

}