With XOR, how do you recover both values when two sequence numbers are dropped?

## Where the single fold stops Folding the expected range together with the received log gives an accumulator in which every delivered number appears twice and cancels. With one number dropped, the accumulator is that number. With two dropped — call them `x` and `y` — the accumulator is `d = x xor y`. That value identifies neither: for distinct sequence numbers it is typically not even a legal sequence number. A candidate who stops here has the right first step and no second one. ## The distinguishing bit The second step is to notice what `d` actually tells you. Bit by bit, `d` has a 1 exactly where `x` and `y` disagree and a 0 exactly where they agree. Two facts follow: - **`d` is nonzero.** If it were zero, `x` and `y` would agree everywhere, meaning they are the same value. Distinct sequence numbers cannot be, so at least one bit of `d` is set. (If your inputs *can* repeat a value, this is the precondition to check first — the technique has nothing to work with when `d` is zero.) - **Any set bit separates them.** Choose one such position and call the test "is this bit set?". `x` answers one way and `y` answers the other, necessarily. The lowest set bit is the conventional choice simply because it is cheap to obtain, but any of them works and none is better than another. ## Why partitioning preserves the cancellation This is the part worth saying out loud, because it is the step that makes the technique correct rather than merely clever. Partition the entire stream — expected values and received values alike — using the chosen bit as the test. A number that appears twice has the same bit pattern both times, so both of its occurrences answer the test identically and land in the same bucket. It therefore still appears an even number of times *within that bucket* and still cancels. Nothing paired ever straddles the partition. The two dropped numbers, by construction of the bit, land in opposite buckets. So each bucket contains many even-multiplicity values and exactly one odd-multiplicity value, which is precisely the situation a plain fold solves. Two accumulators, one per bucket, end holding `x` and `y`. ## Cost and shape One pass to compute `d`, one pass to partition and fold — or a single pass if the stream can be replayed only once and you are willing to buffer nothing, by computing `d` over the expected range in closed form and the received log in the same pass. Time is O(n); extra space is three accumulators plus the chosen bit, so O(1). The order of the input never matters, and because the combining operation is associative, both passes shard cleanly: compute partial accumulators per shard and combine them. Which value ends up in which accumulator is not determined by anything meaningful — you get the pair, unordered. If the caller needs to know which of the two is which, that information has to come from elsewhere. ## Where it stops generalising The natural next question is three unpaired values, and the honest answer is that this construction does not extend. With three, the fold gives `x xor y xor z`, and a set bit in that value no longer guarantees a clean split — it tells you an odd number of the three have the bit set, which is one or all three, and the "all three" case leaves one bucket with three odd-multiplicity values and the other with none. Recovering `k` unpaired values in constant space needs a different instrument altogether — a family of independent parity checks rather than a single one — and at that point the memory saved rarely justifies the machinery over simply keeping counts. ## What the interviewer is testing Not the trick itself, which is memorisable. The signal is whether the candidate can state *why* the partition preserves cancellation, and whether they check that `d` is nonzero before relying on a set bit existing. Those two statements are the difference between having read the technique and understanding it.