DSA interview question

XOR of All Numbers in a Range [L, R]

Medium · Algorithms · Topics: bit manipulation, math

The problem

A checksum routine for a sequential ID allocator needs the XOR of every ID from L to R, and the ranges can span a billion IDs, so looping is too slow. XOR from 1 to n follows a period-4 pattern: n, 1, n + 1, 0 for n mod 4 = 0, 1, 2, 3, because each aligned block 4k, 4k+1, 4k+2, 4k+3 XORs to 0. And like prefix sums, XOR(L..R) = XOR(1..R) ^ XOR(1..L−1), because the shared prefix cancels.

Example: L = 4, R = 8 → 4 ^ 5 ^ 6 ^ 7 ^ 8 = 8.

Function signature

long long findXOR(long long l, long long r);  // 1 <= l <= r <= 10^9

Test cases

Input `(L, R)`	Output	Explanation
`(4, 8)`	`8`	4 ^ 5 ^ 6 ^ 7 = 0, then ^ 8
`(3, 7)`	`3`
`(1, 10)`	`11`	10 mod 4 = 2, so 10 + 1
`(5, 5)`	`5`
`(1, 1000000000)`	`1000000000`	10⁹ mod 4 = 0

(Confirm: 1 ≤ L ≤ R ≤ 10⁹; O(1) per query is expected.)

How interviewers phrase it

"Find the XOR of all numbers from L to R" (GeeksforGeeks), usually after "find XOR of 1 to n in O(1)".

Clarifying questions to ask

Is the range inclusive at both ends? (Yes.)
How large are L and R? (Up to 10⁹, so no loops.)
How many queries? (Many, so O(1) each.)

Follow-ups to expect

"Why the period-4 pattern?"
"Derive the four cases."
"Why XOR(1..R) ^ XOR(1..L−1)?"
"What if L can be 0?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview