XOR of numbers in a given range
MediumPrefix XOR has a four-case pattern
Problem
Return the XOR of all integers from L to R inclusive.
Use the pattern of XOR from 0..n (cycles every 4), then cancel the part before L.
The idea
The XOR of 1..n depends only on n mod 4, following the cycle n, 1, n+1, 0. With that closed form, the XOR of a range is xorTo(R) ^ xorTo(L-1) in constant time instead of a loop.
The trick
- xorTo(n): n%4==0 -> n, 1 -> 1, 2 -> n+1, 3 -> 0.
- Range XOR = xorTo(R) ^ xorTo(L-1), the same shape as prefix sums.
- O(1) rather than O(R-L).
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — L=3, R=9 Values: 3, 9.
1f(n): // XOR of 0..n by n%4: n,1,n+1,02return f(R) ^ f(L-1)Input
- array
- [3, 9]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- L = 3, R = 9
- Output:
- 2
- Explanation:
- XOR of 3^4^...^9 = 2.
Example 2
- Input:
- L = 4, R = 8
- Output:
- 8
- Explanation:
- XOR of 4..8 = 8.
Example 3
- Input:
- L = 1, R = 1
- Output:
- 1
- Explanation:
- Just 1.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.