Find the missing number
This is a very common interview questions and comes in various forms. The most common one is of the following format
Problem 1
Given an array of 999 distinct integers ranging from 1 to 1000 including. Find which number is missing. Restrictions: loop over the array only once, can’t allocate an additional array.
Another version of the problem is where 2 numbers are missing.
Problem 2
Given an array of 998 distinct integers ranging from 1 to 1000 including. Find which 2 numbers are missing.
Restrictions: loop over the array only once, can’t allocate an additional array.
Problem 1:
Find sum of numbers from 1 to 1000 = 1000*1001/2 =500500
Add the current array sum of 999 numbers = S
The missing number = 500500-S
Problem 2:
Find the sum of numbers from 1 to 1000 = 1000*1001/2 = 500500 = S
Find sum of squares of numbers from 1 to 1000 = n*(n+1)*(2n+1)/6 = 333 833 500 = SS
Find sum of 998 distinct numbers as N
Find sum of squares of 998 distinct numbers as NS
Let a and b be 2 missing numbers
S-N=a+b
SS-NS=a^2+b^2
Solve for a and b.