Why does XOR-ing every value in a stream cancel out the values that appear twice?
answer
- what a value folded twice contributes
- the identity element of the operation
- why fold order cannot matter
- each bit ends as a parity count
- even occurrences change no parity
basics
~20 sXOR is self-inverse (x xor x = 0), has identity 0, and is commutative and associative. So the fold can be reordered to put duplicates side by side; every pair collapses to 0 and only the unpaired value survives.
solid answer
~50 sThree algebraic facts do all the work. XOR is self-inverse, so `x xor x = 0`; zero is the identity, so `x xor 0 = x`; and XOR is commutative and associative, so the order I fold the stream in cannot change the result. That last property is the one people skip, and it is what lets me mentally reorder an arbitrarily shuffled log so each duplicated id sits beside its twin — at which point every pair rewrites to 0, and 0 contributes nothing. Folding a day's transfer ids, where each transfer contributes one debit entry and one credit entry, therefore leaves exactly the id that lost its partner. The bitwise view says the same thing: each bit of the accumulator is the parity of that bit across the whole stream, so anything occurring an even number of times contributes nothing. The technique assumes exact pairing — three occurrences survive as one.
go deeper
Recall the three properties by name and be able to state them as equations: self-inverse, identity 0, commutative and associative. Then say in one sentence why they let duplicates cancel in any order.
Explain the mechanism two ways — the algebraic reordering argument and the per-bit parity argument — and state the precondition the technique quietly relies on: everything except the target appears an even number of times.
Show what happens when the precondition breaks in real data: an entry written three times, or two unbalanced ids, both produce a confident wrong answer with no error. Say how you would detect that independently.
Own the framing that this fold trades diagnosability for a constant space bound. Be ready to say when a one-pass constant-space answer is worth a technique that fails silently, and what guardrail you would require alongside it.
## One bit at a time XOR (exclusive or) compares two bits and yields 1 exactly when they differ: `0 xor 0 = 0`, `0 xor 1 = 1`, `1 xor 0 = 1`, `1 xor 1 = 0`. Applied to two multi-bit values it does this independently at every bit position — there is no carry between positions, so bit 5 of the result depends only on bit 5 of the two inputs. That independence is why every claim below can be proved one bit at a time and then simply repeated across the width of the value. ## The three properties that matter **Self-inverse.** `x xor x = 0`. At each bit position the two operands hold the same bit, which never differs from itself, so every output bit is 0. Each value is its own inverse — there is no separate "undo" operation the way subtraction undoes addition. **Identity.** `x xor 0 = x`. A 0 bit leaves the other bit unchanged, so folding zero into an accumulator is a no-op. This is what makes 0 the correct starting value for a fold. **Commutative and associative.** `a xor b = b xor a` and `(a xor b) xor c = a xor (b xor c)`. Both follow from the per-bit definition, which is symmetric in its two arguments. Consequently a fold over a whole sequence has exactly one value, independent of the order the elements arrive in and of how you parenthesise the combining. Taken together these make the set of fixed-width values under XOR an abelian group in which every element is its own inverse — algebraically, a vector space over the two-element field. You do not need that vocabulary in an interview, but it is the reason the trick feels like it is cheating: XOR gives you cancellation without needing an inverse operation, and reordering without needing sorted input. ## Why the pairs vanish Suppose a reconciliation job folds the transfer ids of a day's ledger, where a completed transfer writes its id twice — once on the debit side, once on the credit side — and exactly one transfer was written on one side only. The stream is shuffled: `t3, t9, t3, t7, t7, t9, t4`. Because the fold is commutative and associative, this is the same value as `(t3 xor t3) xor (t7 xor t7) xor (t9 xor t9) xor t4`, which by self-inverse is `0 xor 0 xor 0 xor t4`, which by identity is `t4`. Nothing was sorted, nothing was buffered, and the duplicates never had to be adjacent in the actual input — the reordering happened only in the argument. ## The parity view There is a second explanation worth being able to give, because it generalises better. Fix a bit position, say bit 3. The accumulator's bit 3 flips every time an input has bit 3 set, so at the end it holds the *parity* of how many inputs had that bit: 1 for an odd count, 0 for an even count. A value appearing twice sets each of its bits twice, an even contribution, so it changes no parity anywhere. XOR is bitwise addition modulo 2, and duplicates cancel for exactly the reason that adding anything twice modulo 2 changes nothing. ## What the technique assumes, and how it fails The fold answers one narrow question and answers it silently: - **Everything except the target must have even multiplicity.** If one id appears three times, two occurrences cancel and the third survives — the result looks like a perfectly ordinary answer and you cannot tell the difference. - **Exactly one odd-count value.** With two, the result is their combination, which is usually a value that never appeared in the input at all — a plausible-looking id that identifies nothing. - **A result of 0 is ambiguous.** It is consistent with "everything paired up" and also with several anomalies whose combination happens to cancel. - **No counts, no positions, no records.** The fold cannot tell you how many anomalies there were, where they occurred, or anything else about the offending entry beyond its id. That is the price of the space bound. One pass, O(n) time, O(1) extra space, no buffering, and — because the operation is associative — the stream can be split across shards and the partial accumulators combined afterwards with XOR. ## What it is not XOR is not OR: OR accumulates set bits and never clears them, so an OR fold saturates towards all-ones and tells you nothing. And the fold is not counting: it never learns multiplicities, only their parity. If the question you actually need answered is "which ids are unbalanced, and by how much", parity is the wrong instrument and a counting structure is the right one.
- Does the fold still work if the paired entries are interleaved arbitrarily across the day's log?Yes. Commutativity and associativity mean the fold's result depends only on the multiset of values, not on their order or grouping, so no sorting or buffering is needed. That is precisely why it works on a stream you see exactly once and cannot rewind.
- What does the fold return if one id appears three times instead of twice?Two of the three occurrences cancel and the third survives, so the accumulator holds that id combined with the genuinely unpaired one. If the tripled id is the only anomaly, the result is simply that id — indistinguishable from a correct answer. The fold has no way to signal that its precondition was violated.
- Why fold with XOR rather than with addition?With addition, duplicates do not cancel — you would need a separate subtraction of an expected total, and the running sum can exceed the accumulator's width, which either wraps or needs a wider type depending on the arithmetic you are given. XOR is closed on values of a fixed width, never grows, and each value is its own inverse, so one accumulator is enough.
Like a room where every guest toggles a single light switch on the way in: after everyone has passed through, the switch tells you only whether an odd number of people entered.
saying these in an interview costs you the question
- Claims the duplicates must be adjacent in the input
- Says the stream has to be sorted first
- Confuses XOR with OR and expects set bits to accumulate
- Believes the fold still identifies a value appearing three times
- Thinks the accumulator can overflow the way a running sum can
- Claims the result also tells you how many times each value appeared