Nine numbers sit in an array. Eight of them have exact duplicates somewhere in the list — four pairs, neatly matched. But one number has no partner. It appears exactly once.

This problem — “find the single unique element” — shows up everywhere. It's LC 136, one of the most-asked easy problems, and it's also the foundation for harder variants like “single number II” and “single number III.” The naive solutions are straightforward, but the elegant solution uses a technique you've already mastered.

Your task is to find the loner. At first, the only tool you have is your eyes. Scan the array below and spot it.

You found it by visual scanning — comparing each number against every other. That's essentially an O(n^2) brute force or an O(n) hash set approach. Both work, but both cost something: either time or space. What if you could find the unique element with zero extra memory?

The most natural solution is a Set: iterate once, adding unseen values and removing seen ones. Whatever remains is the loner. The code writes itself — something like const seen = new Set() followed by a loop that toggles membership. It works perfectly: O(n) time, O(n) space.

But that space cost is real. For an array of a million elements, you're allocating a million-entry hash table just to find one number. Every set.add() call is a hash computation, a memory allocation, a pointer chase. The algorithmic complexity is fine, but the constant factors add up — and the O(n) memory is fundamentally unnecessary.

There's a way to do this with a single integer variable and zero extra memory. It relies on everything you learned about XOR in the previous module. Watch both approaches race side by side.

The hash set works but burns O(n) memory. The XOR fold uses O(1) — a single accumulator variable. That's not a minor optimization; it's a fundamentally different approach to the problem. The question is: why does it work?

The space race showed the mystery approach using O(1) memory — a single integer variable, 4 bytes, no hash table. But how can a single integer possibly track which elements have partners and which don't? The hash set approach needs an entire data structure for that bookkeeping.

What happens if you XOR every element in the array into a single accumulator, one at a time? The XOR laws you built in the previous module — self-inverse, identity, commutativity — are about to do something remarkable. But you need to see it unfold step by step to believe it.

Fold the array below and predict what happens at each step. Watch the accumulator carefully — can you spot the moment a pair cancels? Can you predict what the final value will be before you finish?

The pairs vanished and the loner survived. No hash table, no sorting, no nested loops — just one pass through the array with a running XOR. The algebra you built in the previous module isn't abstract theory; it's a concrete algorithm that runs in O(n) time and O(1) space.

Same principle, new array. This time you choose the fold order. Does it matter?

No matter how you ordered the fold, the same element survived. Commutativity and associativity aren't just theoretical properties — they're what make XOR-fold robust against any input ordering. You don't need to sort, partition, or preprocess. Just fold.

A different problem with the same tool — but a twist that reveals how flexible XOR-fold really is. The previous screens found a unique element in an array of duplicates. This problem has no duplicates at all: you're given the numbers 0 through n, but one is missing. You have n numbers instead of n+1. Can XOR find the gap?

The naive approach is summation: compute expected = n*(n+1)/2, subtract the array sum, and the difference is the missing number. That works, but it risks integer overflow for large n — the sum can exceed 32-bit bounds. XOR doesn't have that problem, because XOR-folding never grows beyond the bit width of the largest input.

But XOR-fold worked before because duplicates cancelled. This array has no duplicates — every number appears exactly once (except the missing one). How would you create pairs to cancel? Think about what additional information you have: you know what the complete range 0..n should contain. Can you use that knowledge to manufacture the pairs XOR needs?

XOR-fold found the missing number by cancelling every present value against its expected counterpart. The same O(1) space, O(n) time guarantee. This variant appears as LC 268 — and the one-liner solution is a direct translation of the fold you just performed.

Both algorithms — find-the-unique and find-the-missing — reduce to nearly identical TypeScript. The unique-element finder is arr.reduce((acc, x) => acc ^ x, 0). The missing-number variant XOR-folds the array and then XOR-folds the expected range 0..n, returning whatever doesn't cancel. Build both functions and see how the algebraic insight compresses into minimal code.

Two functions, two reduce calls. The conceptual work happened in the algebra module — the code is just the final translation. This is the pattern with bitwise algorithms: the understanding is the hard part, and the implementation is almost free once you have it.

XOR-fold is elegant but not universal. It requires every element to appear an even number of times except the target. If three values appear once and two appear twice, the fold gives you the XOR of all three singletons — useful, but not a single answer. Similarly, if a value appears three times, it doesn't fully cancel (a ^ a ^ a = a). Identify which problems are XOR-safe and which break the assumption. Knowing the boundary is as important as knowing the trick.