How does XOR find the one dropped sequence number when a receiver logs n-1 of 1..n?
answer
- the received log has nothing to cancel
- supply the missing occurrences yourself
- fold what you expected as well
- delivered numbers now appear twice
- only the dropped one is folded once
basics
~20 sFold the expected numbers 1..n and the received ones into a single XOR accumulator. Every delivered number then appears exactly twice and cancels, so the accumulator ends holding the one sequence number that never arrived.
solid answer
~50 sThe insight is that you manufacture the pairs yourself. The received log has no duplicates in it, so there is nothing to cancel — but if I fold the whole expected range `1..n` into the same accumulator as the received numbers, every delivered number is now contributed exactly twice and vanishes, while the dropped one is contributed only once and survives. It costs one pass, no extra memory beyond the accumulator, and it does not care what order the packets arrived in or whether the log is sorted. Compared with the arithmetic version — expected total minus observed total — XOR never grows a running value beyond the width of the numbers themselves, so there is no overflow question to answer. The preconditions are strict: exactly one number missing, no duplicates, and no corrupted values. If two are missing, the accumulator holds their combination, not either one.
go deeper
Be able to state the construction: fold the expected range and the received values into one accumulator so that everything delivered appears twice. Know that the result is the single value that was never received.
Explain why the pairing is manufactured rather than present in the data, derive the result step by step, and compare it with the arithmetic difference — including why the accumulator's width is never a concern here.
Name the preconditions and what each violation produces: a duplicate, a corrupted value, or a second gap all yield a confident wrong answer. Say what independent check you would run alongside the fold before acting on its output.
Decide when a constant-space, one-pass answer is worth a technique with no error channel, and what the fallback is when the cheap check says the precondition failed on a given window.
## The problem shape A receiver expects sequence numbers `1..n` and logs the ones that arrive. Exactly one never shows up, and you want its number in one pass over a stream that may be far larger than memory. Nothing may be sorted, buffered, or revisited. ## Why the naive fold does not apply directly The XOR fold recovers a value that appears an odd number of times among values that appear an even number of times. The received log does not have that shape at all: every number in it appears exactly once, so folding it alone just produces the combination of everything received — a value with no useful meaning. The move is to supply the missing multiplicity. Fold the *expected* range into the same accumulator: ``` acc = 0 for v in 1..n: acc = acc xor v for each received r: acc = acc xor r ``` Now think about what each number contributes. A delivered number `d` is folded once from the expected range and once from the received log — two contributions, which cancel by self-inverse. The dropped number `m` is folded only from the expected range — one contribution, which survives. Since XOR is commutative and associative, the interleaving of the two loops is irrelevant; you can even fold them concurrently as the packets arrive. ## A trace Take `n = 8` with `4` dropped, so the receiver logs `7, 1, 3, 8, 2, 6, 5` in arrival order. Folding `1..8` gives some value `E`. Folding the received numbers gives `E xor 4`, because the received set is exactly `1..8` minus `4`. Combining the two accumulators yields `E xor E xor 4 = 4`. Notice the arrival order never entered the argument. ## Avoiding the expected pass The first loop is O(n) work that produces a value with a closed form, because the XOR of `1..n` cycles with period four: | n mod 4 | XOR of 1..n | |---------|-------------| | 0 | n | | 1 | 1 | | 2 | n + 1 | | 3 | 0 | So the whole job is one constant-time computation plus one pass over the received log. This is worth knowing not as a memorised fact but because deriving it — group the numbers in fours and observe that each aligned block of four cancels to zero — is a common follow-up. ## Versus the arithmetic approach The sum-based version computes `n(n+1)/2` minus the total received. It is equally correct in exact arithmetic and it carries strictly more information, because the difference is a *magnitude*: with two numbers missing the sum tells you their total while the fold tells you their combination, and having both gives you two independent equations for two unknowns. What the sum costs you is a question about the accumulator's range. A running total over a long log grows without bound in exact arithmetic; mainstream runtimes answer this differently — some fix values at a machine width and wrap silently on overflow, while Python and Ruby promote transparently to arbitrary precision, which is correct but no longer a constant-size accumulator. The XOR fold sidesteps the whole discussion: the accumulator is exactly as wide as one sequence number and never grows, whatever the runtime does with overflow. ## Preconditions, stated out loud The technique is only valid under assumptions that real network logs violate regularly: - **Exactly one number is missing.** With two, the accumulator holds their combination — typically a value that is not a valid sequence number at all, and always one that identifies neither. - **No duplicates.** A retransmitted packet logged twice cancels itself out of the received side, making its number look dropped. - **No values outside the range.** A corrupted sequence number folds in and poisons the result silently. - **The range endpoints are known.** You need `n`; if the receiver does not know how many were sent, there is nothing to fold against. As with every parity-based technique, a violated precondition produces a confident wrong answer rather than an error. In production the fold belongs behind a cheap independent check — for example, comparing the count of received numbers against `n - 1` before trusting the result. ## Cost O(n) time, O(1) additional space, single pass, order-independent, and splittable across shards because the combining operation is associative. That constant-space bound is the entire reason to prefer it over the obvious alternative of marking off a set of seen numbers, which is simpler to debug but needs memory proportional to the range.
- Can you avoid the pass over the expected range 1..n?Yes — the XOR of `1..n` has a closed form with period four: it is `n` when `n mod 4 == 0`, `1` when `n mod 4 == 1`, `n + 1` when `n mod 4 == 2`, and `0` when `n mod 4 == 3`. It falls out of noticing that each aligned block of four consecutive values cancels to zero. That reduces the work to one constant-time step plus a single pass over the received log.
- What happens if two sequence numbers were dropped rather than one?The accumulator holds the combination of the two, which is usually not a valid sequence number and identifies neither. You need a second independent equation — an arithmetic total alongside the fold, for instance — or a partitioning step that separates the two before folding.
- The receiver logged a retransmission twice. What does the fold report?The duplicate cancels itself on the received side, so that number contributes an even count overall and disappears — the fold then reports the combination of the genuinely dropped number and the retransmitted one. This is the failure mode to name: the technique cannot distinguish a violated precondition from a valid answer.
saying these in an interview costs you the question
- Folds only the received numbers and expects an answer
- Says the received log must be sorted first
- Claims the fold detects two dropped numbers at once
- Ignores that duplicates break the technique silently
- Asserts the XOR accumulator can overflow like a running total
- Cannot say what the fold returns when nothing was dropped