I think the editorial has not been written well. From what I have understood by seeing successful submissions is that we are first converting every number A[i] into it’s binary representation and then maintaining a prefix sum array. But I get lost after this and can not comprehend rest of the logic.
Can anyone please explain it in a more lucid way and also the intuition behind why we are doing what we are doing?
In this question we are required to find value of x such that its sum of xor with all number is maximum .
so xor of same bits is zero and that of different bits is one . so what we are doing we represent every number in its binary from now we maintain prefix sum for every index then we check if there are more number of zero or one at any index if number of one are greater than we will add that index to x otherwise we will not add
1 Like
if something is not clear …you can comment that
- Convert given numbers into binary string of at max 31bits.
- Create a new 2D array to store prefix sum of 1’s calculated per bit position.
Traverse through each bit position for all numbers and calculate prefix sum. - Now for a given query l to r, we count the number of 1’s at bit position i for numbers in range l to r using the prefix sum already calculated.
For example, if l to r numbers in binary string are as follows:
**Bit-> …6543210
l-> …01001
l+1-> …10100
.
.
.
r-> …10010
**
4.We have to find smallest integer X such that Al ^ X + Al+1 ^ X+ …Ar ^ X is maximum.
For that we need to maximize each term to the possible extent.
We will maximize each bit from bit 0 to 30.
Hence we find the count of 1’s at bit position i , let’s denote it as c(i) and the count of number of 0’s at bit position i for numbers in range l to r be c’(i).
If c(i)>c’(i), means we can take the i’th bit from back of X as ‘0’ so that its XOR with bit position i with numbers from l to r will retain the maximum number of 1’s .
It means that we will take the opposite bit of which appears maximum times in position i of numbers from l to r.Simply because we need to make maximize 1’s at position i after Xoring each term with X for required sum to be maximum.
And if c(i)==c’(i), we will take 0 as i’th bit of X because we are asked to find smallest integer X
[See my solution][1]
PS: This is my first attempt to write/explain an answer.Please bear with me.
Hope it helps you.
[1]: https://www.codechef.com/viewsolution/17735058
2 Likes
Thank you dude! That was really helpful. And the solution was so simple. Silly me 
1 Like
Thanks. 
Glad my first attempt helped you !