Find the missing sequence number with XOR

Question

An exchange feed stamps each message with a sequence number. A clean session should contain every number from $0$ to $n$ exactly once, but one message was dropped, so the array of received numbers has length $n$ and is missing exactly one value from that range.

received = [3, 0, 1]        # range is 0..3, so 2 is missing
-> 2

Find the missing sequence number in $O(n)$ time and $O(1)$ space. Summing and subtracting works but can overflow on huge ranges; the interviewer wants the XOR version.

Accepted Answer

XOR is self-cancelling: x \oplus x = 0 and x \oplus 0 = x. The full range is 0, 1, \dots, n; the received values are that same set minus one element. XOR the complete range against the received values, and every present number appears twice (once from the range, once from the array) and annihilates, leaving only the missing one. A tidy way to fold both sequences into a single loop: seed the accumulator with n (the largest index, which has no array slot), then XOR each index i and its value together. Tracing [3, 0, 1] with n = 3: start acc = 3; then 3 ^ (0^3) = 0, 0 ^ (1^0) = 1, 1 ^ (2^1) = 2.…

Find the missing sequence number with XOR

Your answer

More Coding questions