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

**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:

#### Subtask 1

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:**

## Comments