Bloomberg interview question

Given an continuous integer array, if there is one number missing, how to find it out without sorting? How about two numbers?

Interview Answers

Anonymous

8 Oct 2011

(max-min)+1 method can only find out the "number" of missing integers, but the particular number value is still unknown. The answer should be: find max and min, assume there is no number missing, get the Sum of the array, then use the Sum of the given array to subtract it. The difference is the missing one. For the case of two missing numbers, build two equations with two variables. one equation comes from the Sum difference, another from product difference

2

Anonymous

8 Oct 2011

find max and min integers in the array and compare to the size of the array. (max - min) + 1 should equal the number of integers in the array if no numbers are missing. if one is missing the array will be short by 1 if two are missing the array will be short by 2, etc.