An array holds n distinct numbers taken from 0 to n, shuffled, so exactly one value is absent. You can find it in one pass with a couple of extra variables: add everything up and compare against the sum you expected, or XOR everything together and let every pair cancel itself.
Write 0 to n forward, then write it again backward underneath. Every column adds up to n, and there are n + 1 columns, so the two rows together hold n(n + 1) and one row holds half of that. Scan the array, subtract what you see from that total, and whatever is left over is the number that never showed up.
How to read this: Top: the numbers 0 to n written forward and backward; each column adds to n (gold). Bottom: the actual array, with each position in tiny numbers above it. As each array number is read, it lights up in the top rows.
Try this: Press Step a few times and watch the Expected − total readout shrink toward the answer.
Fixed-width integers cap the total. Switch to Signed 8-bit, where the largest value is 127, and push n past 10: the product n(n+1) wraps around before it is halved, and for most n the answer comes out wrong.
In Java the value wraps silently. In C and C++ signed overflow is undefined behavior. XOR never carries from one bit into the next, so its register never needs more bits than n itself. Lab 2 shows it.
XOR every index from 0 to n into one register, then XOR every value in the array into the same register. Each present number goes in twice, once as an index and once as a value, and x ⊕ x = 0 wipes it out. The only number that went in once is the missing one, so it is all that remains. Watch the register change one bit at a time.
How to read this: Every number is written in binary: each box is 0 or 1, and the small numbers above (8 4 2 1 and so on) show what each box is worth (1010 = 8 + 2 = 10). XOR flips a register box whenever the incoming bit is 1, so two equal numbers flip the same boxes twice and cancel out.
Try this: Use Step number to feed whole numbers; switch to Step bit to watch single flips.
XOR is associative and commutative, so the order of the scan does not matter. You can regroup the whole chain into matching pairs, each pair collapses to 0, and 0 ⊕ m = m.
Bit by bit it is a parity count: a register bit ends at 1 exactly when an odd number of inputs had a 1 there. Every present number adds two 1s to each of its bit columns, so only the missing number's bits survive.
Three more ways to find the gap, run on the same input. Sorting puts every number in its slot but costs O(n log n). A seen-array is linear but needs n + 1 extra cells. Cyclic sort swaps each value into the slot with its own index, in place, and then the first slot holding the wrong value is the answer. The counters show what each route actually spends.
How to read this: The small numbers on top are slot numbers. A cell turns green once it holds its own slot number; the first slot that can't is the missing number.