226. Find XOR of All Numbers From L to R

Given two integers l and r, find the XOR of every integer from l to r, inclusive.

Input: Two lines: the first contains l, the second contains r. Output: Print a single integer - the XOR of every integer from l to r inclusive.

0 <= l <= r <= 10^9

This is the exact same 'prefix technique' idea as prefix sums for range-sum queries, just using XOR's self-cancelling property (x XOR x = 0) instead of subtraction.

You need to XOR (a bitwise operation) every single number from L to R together. Instead of doing that one number at a time, there's a shortcut pattern based on how XOR from 1 to N behaves. Brute force: Loop through every integer from l to r directly, XOR-ing them all together one at a time - correct, and actually fine for smaller ranges, but too slow when r can be as large as a billion. Optimised: XOR has a neat prefix-style property just like sums do: XOR(l..r) = XOR(1..r) XOR XOR(1..l-1), because XOR-ing the same value twice cancels it out, so everything from 1 to l-1 cancels away, leaving exactly the range l to r. And XOR(1..n) itself has a simple, provable repeating pattern based on n mod 4, so it can be computed instantly with no loop at all.

Define f(n) = XOR of every integer from 0 to n. This function has a well-known 4-cycle closed form based on n mod 4: it equals n when n mod 4 is 0, 1 when n mod 4 is 1, n + 1 when n mod 4 is 2, and 0 when n mod 4 is 3. Since XOR(l..r) = f(r) XOR f(l-1) (the prefix up to l-1 cancels itself out), the whole answer collapses to two O(1) formula evaluations and one XOR, with no loop or per-bit work at all. Time: O(1) Space: O(1)

Work bit by bit instead of number by number: for each of the roughly 30 bit positions, count how many integers in [l, r] have that bit set using the closed-form formula for 'count of numbers up to N with bit b set', applied to both r and l-1 and subtracted. If that count is odd, the result's bit at that position is 1, otherwise 0. This replaces the O(r - l) loop with about 30 constant-time computations, one per bit, which is dramatically faster and still fully general. Time: O(log(max(l, r))) Space: O(1)

Iterate over every integer from l to r and XOR them all into a running result. This is the most direct reading of the problem statement and is trivially correct, but with r up to 10^9 the loop can take up to a billion iterations, which is far too slow to run in a reasonable time limit. Time: O(r - l) Space: O(1)

1. Define a helper: the XOR of every integer from 1 up to some number n. 2. This helper follows a simple repeating pattern based on n divided by 4's remainder: the result is either n itself, 1, n+1, or 0, depending on that remainder. 3. XOR of the range [l, r] equals helper(r) XOR helper(l - 1) - exactly like how a prefix sum lets you get a range sum by subtracting two prefix totals, but using XOR instead of subtraction. 4. Compute both helper values using the pattern, then XOR them together for the final answer.

Time: O(1) - a small fixed number of arithmetic operations, regardless of how large l and r are. Space: O(1) - no extra storage needed at all.

Test l = r (a single-element range), l = 0, and r as large as 10^9 to confirm the f(n) mod-4 pattern is used instead of looping the whole range.

Knowing the XOR(1..n) mod-4 pattern by heart is a genuinely common 'trick question' in bit-manipulation interview rounds - it's worth memorizing the four cases (result is n, 1, n+1, or 0) rather than re-deriving them under pressure.