Skip to content

Finding two absent numbers between 1 and 100

Question

You receive 9898 different integers, all between 11 and 100100, so exactly two values are missing. How can you identify the two missing numbers efficiently?

Short answer

Use the sum and the sum of squares in one O(n)O(n) pass. If x,yx,y are missing, x+y=5050−∑aix+y=5050-\sum a_i and x2+y2=338350−∑ai2x^2+y^2=338350-\sum a_i^2. Then xy=12((x+y)2−(x2+y2))xy=\tfrac12\left((x+y)^2-(x^2+y^2)\right), so x,yx,y are the roots of a quadratic. A boolean array of size 100100 also works in O(n)O(n) time with O(n)O(n) space.

Adapted from Zhou, A Practical Guide to Quantitative Finance Interviews, sec. 2.5 Series Summation, 'Missing integers', p.17; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question