dimator | head

I love programming interview questions. The last cool one I got was the following:

Find the missing number out of an array of 999,999 elements, with the numbers from 1 to 1,000,000 randomly distributed in it, with one missing number.

There are different methods, of course, and I was asked to successively give a better answer, along with space and time complexity.

(If you want to figure this out for yourself, stop here.)

Method 1
Use quicksort to sort the array in place, traverse to find the missing number.
Time complexity: quicksort is O(n lg n), space complexity: already allocated.

What if we had infinite memory resources? Could we improve the run time?

Method 2
Allocate another array of size 1,000,000 elements, initialized to some sentinal value. Starting at array index 0, use the number in the original array as an array index into the new array, and store the number in the second array. What we’ve done is simply created a hash.
Traverse to find the sentinal; the location is the missing number. Initialization, population, traversal, each run O(n), space O(n).

What if we only had enough memory to fit 1 other number? Can we still find the missing number?

Method 3
Just sort in place with one integer at a time, swapping number at arr[i] with contents of arr[arr[i]]. If arr[i] == i, i++. Continue until whole array is sorted. Now traverse as before to find the missing number. (It turns out this method is not entirely error free, as certain inputs would give the wrong answer, but it demonstrates the point.)
Time complexity O(n), and traversal to find missing number, O(n). Space: just one temporary variable.

Pretty nice. Any other methods? I’m sure there are others, but the most elegant one (that I did not think of) was as follows:

Method 4
The sum of all the numbers from 1 to n has a closed form:

So, sum all numbers in the array, and subtract from the above to find the missing number. How clever! Stuff like this gets me going.