question
An array is filled with the numbers from 1 through 100 (inclusive), with the
exception of one missing number. The array has been filled randomly with each number
used only once.
What is the fastest way to determine the missing number?
What is the fastest way to determine the missing number?
Answer is O(n).
First calculate the sum of the numbers from 1 through 100 using summation formula ( Σ = [n * (n+1)] / 2 where n = 100).
Iterate through the given list storing the sum of the numbers. Subtract the sum of
given integers from the calculated summation.