XOR of Numbers in a Given Range
XOR of Numbers in a Given Range: given two integers l and r, return the XOR of every integer from l to r inclusive, in constant time.
- 0 <= l <= r <= 10⁹
- Must run in O(1) — the pattern of XOR from 0 to n repeats every 4
Intuition
Xor of numbers in a given range computes the XOR of every integer from L to R. Looping over the range is O(R − L) and too slow when the bounds are large.
The first move is the standard prefix trick. Define f(n) as the XOR of everything from 0 to n. Then:
- The XOR from L to R is f(R) XOR f(L − 1), because XORing the prefix up to L − 1 cancels it out of the prefix up to R.
Self-cancellation is what makes this work — every term below L appears twice and vanishes. Subtraction has no equivalent here; XOR is its own inverse, which is the property being used.
That leaves computing f(n) quickly, and there is a pattern with period 4:
When n % 4 == 0 the answer is n; when n % 4 == 1 it is 1; when n % 4 == 2 it is n + 1; and when n % 4 == 3 it is 0.
The pattern arises because any four consecutive integers starting at a multiple of 4 XOR to zero — the lower bits cycle through all combinations and cancel, leaving nothing.
So f(n) is a constant-time lookup on n % 4, and the whole problem becomes two such lookups and one XOR.
The edge case is L = 0, where f(L − 1) becomes f(-1). Handling it as f(-1) = 0 is correct, since XORing nothing is zero — but many implementations index negatively instead and produce garbage.
The result is O(1) in both time and space, independent of how large the range is.
XOR of 0..n cycles with period 4: n, 1, n+1, 0 for n % 4 equal to 0, 1, 2, 3. Given that closed form, a range becomes f(r) ^ f(l-1) — the same prefix-difference trick as prefix sums, with XOR playing the role of subtraction because it is its own inverse.
Approach
Before reading on: price up what the direct approach costs here, then ask which operator makes the unwanted values cancel themselves out. Aim for O(1) time and O(1) space.
Reduce to prefix XORs
The range XOR is f(R) XOR f(L − 1), where f(n) covers 0 to n. Terms below L appear twice and cancel.
Use XOR's self-inverse property
XOR is its own inverse, so XORing the lower prefix removes it exactly. There is no subtraction equivalent — this property is what the trick relies on.
Find the period-four pattern
f(n) is n when n % 4 == 0, 1 when 1, n + 1 when 2, and 0 when 3. Four consecutive integers from a multiple of 4 XOR to zero.
Compute f in constant time
A single lookup on n % 4 replaces the entire loop, making each prefix O(1) regardless of magnitude.
Handle L equal to zero
f(L − 1) becomes f(-1), which is 0 — XORing nothing yields zero. Indexing negatively instead produces garbage.
Cost of the approach
Two constant-time lookups and one XOR give O(1) time and O(1) space, independent of the range's size.
Solution & live demo
Common pitfalls
Looping over the range
for i in range(l, r + 1): ans ^= i
return f(r) ^ f(l - 1)
Correct but O(r − l), which is far too slow when the bounds reach 10^9. The period-4 pattern answers any range in constant time.
Using f(l) instead of f(l - 1)
return f(r) ^ f(l)
return f(r) ^ f(l - 1)
The prefix must exclude l itself so that l survives in the range. Cancelling f(l) removes it, giving the XOR of l+1..r.
Getting the residue table wrong
if m == 2: return 0 if m == 3: return n + 1
if m == 2: return n + 1 return 0
The cycle is n, 1, n+1, 0. Swapping the last two entries produces answers that are right for half the inputs, which is exactly the kind of bug that survives light testing — verify against a brute-force loop for small n.
Edge cases
f(0) must return 0 — the XOR of an empty prefix. With 0 % 4 == 0 the multiple-of-4 branch returns 0, so the formula needs no special case.
The answer is that single number. f(r) ^ f(r-1) cancels everything below r and leaves r itself.
Nothing loops, so r can be as large as the integer type allows without any change in running time.