XOR of Numbers from L to R
Solve this Probleml and r, compute the XOR of every integer in that closed range — l, l + 1, all the way through r — combined into a single value.
Walking the range one integer at a time works, but there's a shortcut: the XOR of every integer from 1 up to any n follows a fixed 4-step cycle based on n's remainder mod 4. Once that shortcut gives the running XOR up to any single number instantly, the range [l, r] is just the difference between two such running totals — one up to r, one up to l − 1 — since combining the same prefix with itself would cancel it out completely.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ l ≤ r ≤ 10⁹
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — XOR Every Number in Range
BruteWalk from l to r one integer at a time, folding each one into a running XOR. Simple and always correct, but for a range spanning close to a billion numbers, that's up to a billion XOR operations just to answer a single query.
O(r − l)O(1) extra1class Solution {
2 public int rangeXor(int l, int r) {
3 int result = 0;
4 for (int i = l; i <= r; i++) {
5 result ^= i;
6 }
7 return result;
8 }
9}Optimal — Prefix XOR Formula
OptimalThe XOR of every integer from 1 up to n collapses into one of only four possible outcomes, decided entirely by n modulo 4 — n itself, 1, n + 1, or 0. Once that running total up to any n is available in constant time, the XOR of a range [l, r] falls out from combining the running total up to r with the running total up to l − 1 — XOR-ing the same prefix against itself twice would cancel it, so this leaves exactly the numbers between l and r.
O(1)O(1)1class Solution {
2 public int rangeXor(int l, int r) {
3 int xorUpToR = xorUpTo(r);
4 int xorUpToLMinus1 = xorUpTo(l - 1);
5 return xorUpToR ^ xorUpToLMinus1;
6 }
7
8 private int xorUpTo(int n) {
9 int mod = n % 4;
10 if (mod == 0) return n;
11 if (mod == 1) return 1;
12 if (mod == 2) return n + 1;
13 return 0;
14 }
15}