## Editorial for SGS Programming Challenge P1 - XOR in Computer Class

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Snowfall

Because is never greater than , each only has one bit. If we XOR a bit by , the bit will flip. If we XOR it by , it will stay the same. Thus, there are two options for one bit: not changing it or flipping it. Applying this to all bits in one position, all bits either remain unchanged (if is ) or are flipped (if is ). To calculate the subarray sums, we observe that the sum of all subarrays can be calculated using the formula . We calculate the sums for when the bit is flipped and when it is not to check which is larger.

Time complexity: #### Full solution

We can observe that the bits are independent, thus we can use our subtask 1 solution on each bit position separately, multiplying our answer by for the bit (this is the value of that bit) and adding the product to .

Time complexity: 