XOR of Number Range
JavaView on GFG
Problem Overview
The XOR of every integer from 1 through n follows a short cycle of length 4.
Intuition
The XOR of every integer from 1 through n follows a short cycle of length 4. When n modulo 4 is 0 the prefix XOR equals n, when it is 1 the prefix equals 1, when it is 2 the prefix equals n plus 1, and when it is 3 the prefix equals 0. Because XOR cancels identical prefixes, the XOR of the closed range from l to r is exactly the prefix through r XOR the prefix through l minus 1. That formula answers the query in constant time without walking the interval.
Algorithm
- 1Define a helper that maps n to the XOR of 1 through n using n modulo 4.
- 2Return xorUpto(r) XOR xorUpto(l minus 1).
- 3Treat the empty prefix for l equals 1 as xorUpto(0), which is 0.
Example Walkthrough
Input: l = 4, r = 8
- 1. xorUpto(8) is 8 because 8 modulo 4 is 0.
- 2. xorUpto(3) is 0 because 3 modulo 4 is 3.
- 3. 8 XOR 0 equals 8, which matches 4 XOR 5 XOR 6 XOR 7 XOR 8.
Output: 8
Common Pitfalls
- • Use the prefix through l minus 1, not through l. Including l twice would cancel it out of the range.
- • The cycle depends on n modulo 4. Off by one in the residue cases flips every answer.
- • xorUpto(0) must return 0 so ranges that start at 1 stay correct.
- • A loop from l to r is correct but too slow when the bounds are large. Prefer the constant formula.
XOR of Number Range.java
Java
// Approach: XOR from 1 to n repeats every four values: n, 1, n + 1, or 0
// according to n mod 4. The range XOR from l to r is then xor(r) xor xor(l - 1),
// because the shared prefix cancels. No loop over the range is needed.
// Complexity: O(1) time, O(1) extra space.
class Solution {
public int findXOR(int l, int r) {
return xorUpto(r) ^ xorUpto(l - 1);
}
private int xorUpto(int n) {
return switch (n & 3) {
case 0 -> n;
case 1 -> 1;
case 2 -> n + 1;
default -> 0;
};
}
}
Was this solution helpful?