Can you explain why initial sum tells about parity of least significant bit
Since 2^20 does not affect the lsb, if the initial sum is odd, the parity of lsb is odd else it is even.
To understand this, you need to understand the relation between Bitwise XOR and Binary addition.
Bitwise XOR and BInary addition are very similar. The only difference is that we do not consider carries generated in Bitwise XOR. XOR and Addition of two numbers will be the same if no carry is generated at any position.
Now coming back to your question, when we are asking a query 2^20 all the bits at positions 0 to 19 are not affected. If you were to add N numbers then the parity at LSB after performing addition and XOR will always be the same because on LSB no carry is generated upfront.
Really nice approach.
Can anyone explain to me why 1048576 is multiplied with n (which is N btw) ? Since we don’t know how many set bits (at 20th bit) are there in k = 1048576 query.
Thank you for explaining this in a very easy way.
Its totally amazing approach
The link to the problem in the practice section is wrong.
Appreciate your approach. Can you tell me how to build such problem solving skills?
I am definitely the wrong person to ask this. But i can tell you my thought process behind this one.
Nothing, really. Just computed the matrices for n = 3, 4, and noticed that everything off the diagonal was a power of 2, and the diagonal elements were something times a power of 2, which I tried to generalize, and my conjecture just worked out in the end.
