Practice :
Contest Page :
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;
}