Editorial for XORNEY - PELT2019

Question Code: XORNEY

Prerequisites: Implementation

Problem Setter: tds115

Difficulty: Cakewalk

Explanation:
Given two integer l and r, you have to find if xor from l to r is even or odd. Basically, you have
to find the number of odd integer between l and r. Since xor of odd 1’s is 1 and xor of even
1’s is 0. You can make 2 cases:-
(Let count be the number of odd’s)
If l is even and r is even-> count=(r-l)/2
Else -> count=(r-l)/2+1
If count is even then ans is even
Else odd.

Complexity-O(1) for each query

Author’s solution: https://ideone.com/GUjqC5

1 Like

Given that this is a simple problem, it probably needs a more basic explanation.

If we have a “running total” that we are xor’ing numbers into, the parity (even/odd) only changes when we xor an odd number into it, because parity only depends on the bottom binary bit.

One odd number makes the running total odd; two odd numbers flip it back to even.

So - as you say - we are determining how many odd numbers there are between L and R inclusive.

If L & R are both even, this is easy: (R-L)/2 gives the number of odd numbers in range (try it!)

If L is odd, we can drop L down to the even number below (L-1) without changing the count of odd numbers in range. And if R is odd, we can increase R to the even number above without changing the count. So we can get to two even numbers to use the above formula.

And we can do those adjustments automatically using modulo results (%), since a%2 is zero for even a. So we can take C = ((R+R%2) - (L-L%2)) /2 for the count of odd numbers in range.

Then the parity of C is the answer, C%2 == 0 is “Even” and C%2 == 1 is “Odd”.