Finding two absent numbers between 1 and 100
Question
You receive different integers, all between and , 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 pass. If are missing, and . Then , so are the roots of a quadratic. A boolean array of size also works in time with 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