Two Missing Integers

You are given 98 distinct integers, each in the range 1 to 100, so exactly two values in that range are missing. What is a good way to find the two missing integers, reading the data only once and using little extra memory?

Reveal solutionHide solution

#Two equations from two totals

Call the missing values $a$ and $b$ . The full set 1 to 100 has known totals

\sum_{k=1}^{100} k = 5050, \qquad \sum_{k=1}^{100} k^2 = 338350. \tag{1}

Add up the 98 numbers you hold and their squares in a single pass, then subtract,

a + b = 5050 - \sum x, \qquad a^2 + b^2 = 338350 - \sum x^2. \tag{2}

The full set 1 to 100 has a known sum of 5050 and a known sum of squares of 338350. Subtracting the totals of the 98 numbers you hold gives the sum and the sum of squares of the missing pair, and that pair of equations has a single positive solution.

#Solve the pair

Write $p = a + b$ and $q = a^2 + b^2$ . Their difference is recovered through

(a - b)^2 = 2q - p^2 \;\Longrightarrow\; a - b = \sqrt{2q - p^2}, \tag{3}

and then $a = \tfrac{1}{2}(p + \sqrt{2q - p^2})$ and $b = \tfrac{1}{2}(p - \sqrt{2q - p^2})$ . One pass, two running totals, constant extra memory.

#The overflow-free variant

If the squares feel large, exclusive-or carries the same information with no growth. Let

v = \big(1 \oplus 2 \oplus \cdots \oplus 100\big) \oplus \big(x_1 \oplus \cdots \oplus x_{98}\big) = a \oplus b. \tag{4}

Since $a \ne b$ , the value $v$ has at least one bit set. Pick any such bit and split all of 1 to 100 together with the data into the group where that bit is 1 and the group where it is 0. Each group contains exactly one missing number, so the running xor of each group hands you $a$ and $b$ directly.