XOR of a Given Range

Given two integers l and r, return the bitwise XOR of every integer in the inclusive range [l, r] — that is, l ^ (l+1) ^ (l+2) ^ ... ^ r.

Hints

· Stuck? Reveal one nudge at a time.

Looping the whole range is O(r - l) — too slow when the range spans a billion.

Think prefix sums, but with XOR: XOR(l..r) = F(r) XOR F(l-1), where F(n) = XOR(0..n).

F(n) repeats every 4: n, 1, n+1, 0 for n % 4 = 0, 1, 2, 3.

Common doubts

F(r) is XOR(0..r) and F(l-1) is XOR(0..l-1). They share the terms 0..(l-1), which cancel under XOR, leaving exactly l..r.

Pairing consecutive numbers (2k) ^ (2k+1) = 1 makes the running XOR cycle: it returns to 0 at every n where n % 4 == 3, which fixes all four cases.

Using F(l) would cancel the element l itself. F(l-1) keeps l in the range, so the result covers [l, r] inclusive.

Interview follow-ups

· What an interviewer asks next.

The same F(n) formula answers each query in O(1) with no preprocessing, since F has a closed form — no prefix array needed.

Split by residue: the evens and odds each form their own arithmetic pattern, and XOR of an arithmetic-by-2 sequence has its own small closed forms you can derive the same way.

Fun facts

The pattern exists because (2k) ^ (2k+1) = 1 for every k, so consecutive pairs collapse to a single 1 that then cancels.
The same prefix-XOR idea powers XOR range queries over arrays and is the backbone of many competitive-programming bit tricks.

Asked at

AmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: l = 1, r = 4
Output: 4
1 ^ 2 ^ 3 ^ 4 = 4.

Example 2

Input: l = 3, r = 9
Output: 2
3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 = 2.

Example 3

Input: l = 5, r = 5
Output: 5
A single-element range is just that element.

Constraints

- 1 <= l <= r <= 10^9

XORing a whole range one number at a time works, but for a range up to a billion wide it's far too slow. The escape is a small, beautiful fact: the running XOR 0 ^ 1 ^ 2 ^ ... ^ n repeats on a period of four. Once you know XOR(0..n) in O(1), any range answer is two lookups.

Prerequisites

Before you start

· Concepts used directly in the solution.

XOR cancellation. x ^ x = 0 and x ^ 0 = x — repeated values cancel, which is what makes the pattern collapse.

Prefix trick. Turning a range query into two prefix queries: f(l..r) = F(r) ^ F(l-1).

Modular arithmetic. Reading n mod 4 to pick which case of the pattern applies.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The range

“Is the range inclusive of both ends?”

Yes — both l and r are included in the XOR.

“How large can l and r be?”

Up to about a billion, so a per-element loop can be far too slow — an O(1) formula is the target.

The prefix idea

“Why does F(l-1) remove the unwanted part?”

Because everything below l appears in both F(r) and F(l-1) and cancels under XOR, leaving exactly l..r.

The ideal opening — say it like this

XOR of a range is like a prefix sum: XOR(l..r) = prefix(r) XOR prefix(l-1).

And prefix(n) = XOR of 0..n has a period-4 closed form.

So both prefixes are O(1), and the whole thing is constant time.

Understand the problem

The period-4 pattern of F(n) = XOR(0..n)

n:     0  1  2  3   4  5  6  7   8  9 ...
F(n):  0  1  3  0   4  1  7  0   8  1 ...
              ^-- every n % 4 == 3 resets F(n) to 0

n % 4 == 0 -> n
n % 4 == 1 -> 1
n % 4 == 2 -> n + 1
n % 4 == 3 -> 0

Key observations

1Aha

A range XOR is a difference of prefixes

Just like sums, XOR(l..r) = F(r) ^ F(l-1). The shared prefix 0..(l-1) cancels itself, isolating the range you want.

2Aha

F(n) has a closed form

Grouping consecutive numbers shows F(n) cycles every four: n, 1, n+1, 0 for n % 4 = 0, 1, 2, 3. That makes F(n) an O(1) table lookup — no loop.

3Aha

Two lookups, constant time

With F in O(1), the whole answer is F(r) ^ F(l-1) — two evaluations and one XOR, independent of how wide the range is.

Brute force vs optimal

	Loop the range	Prefix XOR formula
Idea	XOR every integer from l to r	F(r) ^ F(l-1) via the period-4 closed form
Time	O(r - l)	O(1)
Space	O(1)	O(1)

Both use constant space, but only the formula is independent of the range width — essential when r - l can be a billion. Full code is in the Approaches selector below.

Summary

Key takeaway

XOR over a range is a prefix problem: XOR(l..r) = F(r) ^ F(l-1), where F(n) = XOR(0..n) has the period-4 closed form n, 1, n+1, 0 for n % 4 = 0, 1, 2, 3. That turns a billion-step loop into two table lookups.

F(n):
    n % 4 == 0 -> n
    n % 4 == 1 -> 1
    n % 4 == 2 -> n + 1
    n % 4 == 3 -> 0
answer = F(r) XOR F(l - 1)