Home
> Algorithms > Given an array of 998 distinct integers ranging from 1 to 1000 including. Find which 2 numbers are missing

## Given an array of 998 distinct integers ranging from 1 to 1000 including. Find which 2 numbers are missing

July 7, 2012

**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.**

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.

Advertisements

Categories: Algorithms