Find the Missing Number in an Array: Sum Formula Solution
Developer interview question on algorithms and complexity
The riddle
An array contains the integers from 1 to n, except one, and its elements are in no particular order. You know the value of n, but neither the missing number nor the order of the elements. How can you find the missing number as efficiently as possible?
Need a hint?
Think of an arithmetic property of the sequence of integers from 1 to n that lets you recover the missing element without searching for it.
Show the answer and the solution
Answer: Subtract the sum of the array's elements from the expected sum n(n+1)/2: the difference is the missing number, in O(n) time and O(1) extra memory.
The reasoning
The sum of the integers from 1 to n is n(n+1)/2, a formula that only needs to be computed once. If you add up all the elements present in the array, exactly the missing number is absent from that sum, so the actual sum is lower than the expected sum by precisely that number. The difference between the two sums directly gives the value sought. The calculation goes through the array only once, so the complexity is O(n) in time, and only a few variables are needed, that is O(1) extra memory. Another method, just as efficient, is to take the exclusive OR (XOR) of all the numbers present together with the numbers from 1 to n: the result is the missing number.
What next?
Reasoning improves like memory: by practising often. Next, test yourself on our general knowledge quizzes.