PROBLEM LINK:
Author, Tester & Editorialist: Ashish Prasad
DIFFICULTY:
SIMPLE - EASY
PREREQUISITES:
PROBLEM:
You are given a positive integer N which is equal to the bit-wise xor of some numbers. There exists an array A of length 64 which contains the count of set bits at respective indices of all those numbers from which integer N was computed.
1 0 1 0 1 .....
0 1 1 1 1 .....
1 1 1 1 1 .....
--------------------------
2 2 3 2 3 ..... upto index 63
The above formed array of count of set bits is represented as array A for some numbers whose bit-wise xor is given as N. Now you need to compute the xor-value which is defined as,
xor-value = (bit-wise xor of all the elements of Array A) \oplus bit-length(N)
where, \oplus is bit-wise xor operator
As this xor-value can be large enough, so you just need to output xor-value modulo 2.
Note: Bit-length or bit width is the number of binary digits, called bits, necessary to represent an integer as a binary number.
EXPLANATION:
The question says that we need to find an answer by doing modulo 2 which means that we need to consider only the least significant bit of xor-value as that will tell whether a number is odd or even. If even then the answer will be 0 otherwise 1. As we are required to find out whether the xor-value is odd or even so we need not to calculate the exact value for elements in array A. We just need to find that the count of set bits at a particular position is odd or even. Getting the count of odd and even can help to get the bitwise xor of all the elements of Array A and then get the answer for our query (modulo with 2).
Let’s take a sample input:
Input : 5
Binary Representation : 1 0 1
Indexing : 0 1 2
Now for count of set bits of unknown number at 0 and 2 index must be odd and that at 1 index must be even because :
- Xor of even number of 1 will be 0
- Xor of odd number of 1 will be 1
Now we got to know that nature of elements (whether even or odd) in count Array A.
If we xor the values in count array A i.e., xor of two odd values and one even value will give value which is even. Now, we xor it with bit length which 3 here (even value xor odd value will give odd value). Finally the odd value modulo 2 will be 1 which is the answer for this sample test case.
SOLUTIONS:
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main () {
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
int o = 0;
int k = (int)log2(n) + 1;
while(n > 0) {
if(n & 1)
o++;
n = n >> 1;
}
o = o % 2;
if(k & 1) {
if(o == 0)
cout << 1 << "\n";
else
cout << 0 << "\n";
}
else {
cout << o << "\n";
}
}
}
Well this was my approach, feel free to share your approach here. Suggestions are always welcomed.