5050 Minus the Total, in One Pass

Sorting the list finds the gap and is merely wasteful, which is why the article says so rather than striking it out. The subtraction works because 5050 is a closed form available before the list is read, and the two conditions carrying it are distinctness and a known range. The article adds the duplicate-hunting mirror image, the sum-of-squares route when two values are absent, and the exclusive-or accumulator for when the total would overflow.

A list holds ninety-nine distinct integers, every one of them somewhere between 1 and 100. Exactly one value from that range never appears. Find it, reading the list once.

The answer is 5050 minus the total of the list, and the interesting part is not the subtraction. It is that 5050 is available before the list has been looked at.

The route that works and is slow

Sort the list, then walk it and report the first position whose value does not match its index. This is correct. It is worth saying plainly, because a candidate who is told his answer is wrong when it is merely expensive learns the wrong thing. Sorting really does find the gap, on all one hundred possible removals at $n = 100$ and on all 1,829 instances for $n$ from 2 to 60, both checked by exhaustion.

What it costs is a comparison sort, so $O(n \log n)$ time, and it either rewrites the caller’s array or allocates a copy of it. Both are avoidable, and the reason they are avoidable is that the question already told you the answer to something you were about to measure.

The total you already know

Nothing in the problem requires knowing which particular values arrived. Only what they add up to. And the complete range from 1 to 100 has a total that is a closed form rather than a measurement:

\sum_{k=1}^{n} k = \frac{n(n+1)}{2}, \qquad \sum_{k=1}^{100} k = \frac{100 \cdot 101}{2} = 5050

(1)

The pairing argument behind it is the one Gauss is supposed to have found as a schoolboy. Fold the range in half and match the smallest to the largest: 1 with 100, 2 with 99, and so on. Every pair sums to 101, there are fifty of them, and fifty times 101 is 5050. No addition of a hundred terms happens anywhere.

Fig. 1 — Fifty pairs, each worth 101. The total of the full range is a formula, not a computation.

One linear equation in one unknown

Call the absent value $m$ . The list is the full range with $m$ taken out, so its total is $5050 - m$ , whatever $m$ happens to be. That is an equation, and it has one unknown:

m = 5050 - \sum_{i=1}^{99} a_i

(2)

One pass over the list, one accumulator, and the answer. The instrumented version of this reads 99 entries and keeps two live scalars, and it does not care what order the values arrive in.

Fig. 2 — The list is read once into a single total. The number you are looking for is the distance between that total and the one arithmetic already gave you.

Generalising costs nothing. For the range 1 to $n$ with one value absent:

m = \frac{n(n+1)}{2} - \sum_{i=1}^{n-1} a_i

(3)

The two conditions that carry the trick

What the subtraction needs

The values must be distinct, and the range must be known before the list is read. Drop either one and equation (2) stops returning anything meaningful.

Distinctness is the condition people forget. If repeats are allowed, a list of ninety-nine values from 1 to 100 can be missing several numbers while some other number appears twice, and a single total no longer identifies anything. A list totalling 5013 might be missing 37, or it might be missing both 40 and 60 while carrying a second copy of 63. One equation cannot separate those.

Knowing the range in advance is the whole content of the method. If you were handed ninety-nine arbitrary integers and asked which one from an unspecified set was absent, there would be nothing to subtract from.

The same equation, read the other way

Turn the problem around: a list holds 101 values from 1 to 100, so exactly one of them appears twice and nothing is absent. Find the repeat. The total is now $5050 + d$ where $d$ is the duplicated value, so:

d = \sum_{i=1}^{101} a_i - 5050

(4)

Same closed form, same single pass, opposite sign. It is the same equation because the underlying model was never about gaps or repeats. It was about a known total and one unknown perturbation of it, and any perturbation you can write as a single number is recoverable from a single sum. That is a better way to hold the trick in memory than either of its two phrasings.

Two values missing, and the second equation

Suppose two values are absent instead of one. The sum gives you $m_1 + m_2$ , and one equation in two unknowns has infinitely many solutions. The fix is to collect a second statistic in the same pass, and the sum of squares is the natural one:

m_1 + m_2 = S_1, \qquad m_1^2 + m_2^2 = S_2, \qquad \sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}

(5)

Two symmetric equations, so $m_1$ and $m_2$ are the roots of a quadratic: their sum is $S_1$ and their product is $(S_1^2 - S_2)/2$ . Still one pass, still constant memory, now with two accumulators. The pattern extends, and the reason it keeps working is that the power sums determine the elementary symmetric functions, which determine the multiset of missing values.

Where the sum is the wrong accumulator

At $n = 100$ the total is 5050 and nothing can go wrong. At large $n$ the sum $n(n+1)/2$ grows like $n^2$ , and in a fixed-width integer type it can overflow before the pass finishes. The honest alternative keeps the same shape and swaps the operation:

m = \Bigl(\bigoplus_{k=1}^{n} k\Bigr) \oplus \Bigl(\bigoplus_{i} a_i\Bigr)

(6)

Exclusive-or is its own inverse and every value appears an even number of times across the two halves except the absent one, which appears once. The accumulator never grows beyond the width of a single entry, so nothing overflows. It costs one pass over the range as well as one over the list, which is why the sum is still the better choice whenever it fits.

Sources and further reading

The closed form and the pairing argument — Triangular number
The general series this is a case of — Arithmetic progression
The one-pass, constant-memory setting — Streaming algorithm
Why power sums pin down the missing multiset — Newton's identities

The problem has exactly one hundred instances at $n = 100$ , so it was settled by running all of them rather than by sampling. Both routes were compared on every instance, and the subtraction was instrumented to confirm 99 reads and two live scalars.