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.

December 16, 2011

Problem : 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.

Solution :

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
%d bloggers like this: