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.
Intuition
This is not an algorithm you derive under pressure — it is a pattern you have to have seen. Write out the XOR of 1..n for the first ten values of n and the result depends only on n mod 4: it cycles through n, 1, n+1, 0. That gives XOR of 1..n in O(1). Extending it to an arbitrary range is the prefix trick you already know from prefix sums, except that XOR is its own inverse: f(r) ^ f(l-1) cancels everything below l because each shared value appears twice.
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
Solve the easier problem first: XOR of 1..n
Ignore l for a moment and just compute the XOR of 1 through n. The brute force is a one-line loop, O(n). To beat it, tabulate: n=1 gives 1, n=2 gives 3, n=3 gives 0, n=4 gives 4, n=5 gives 1, n=6 gives 7, n=7 gives 0, n=8 gives 8, n=9 gives 1. Group them in fours and the structure is obvious.
Read the pattern off the table
Every n with n % 4 == 1 gives 1 (n = 1, 5, 9, 13...). Every n with n % 4 == 2 gives n + 1 (n = 2 gives 3, n = 6 gives 7, n = 10 gives 11). Every n with n % 4 == 3 gives 0. And every multiple of 4 gives n itself (4, 8, 12). Four branches, no loop, O(1). Call this function f(n).
Turn the range into two prefixes
For the range l..r, note that f(r) is the XOR of 1..r, which is the XOR of 1..l-1 followed by the XOR of l..r. Since XOR undoes itself, XOR-ing f(r) with f(l-1) cancels the entire 1..l-1 portion — each of those values appears once in each operand and x ^ x = 0. What survives is exactly the XOR of l..r. So the answer is f(r) ^ f(l-1), two constant-time calls.
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.