DDSA Solutions

XOR of Number Range

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

  1. 1Define a helper that maps n to the XOR of 1 through n using n modulo 4.
  2. 2Return xorUpto(r) XOR xorUpto(l minus 1).
  3. 3Treat the empty prefix for l equals 1 as xorUpto(0), which is 0.

Example Walkthrough

Input: l = 4, r = 8

  1. 1. xorUpto(8) is 8 because 8 modulo 4 is 0.
  2. 2. xorUpto(3) is 0 because 3 modulo 4 is 3.
  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?