Missing Number in an Array
We have an array of N-1 numbers which holds numbers from 1 to N but a missing one. The array is unsorted and in random order. What is the fastest way we can find the missing number?
If we do the best sorting it will be of order n log n. Then we can do a linear search of order n.
Is there a faster way to find the number? We can use another array of size N. For each number in the first array as we do a linear traversal we can set a flag in the second array in that position to true and finally the only index not set to true should be the missing number.
What about not even using the extra memory? Using some maths. Some of first N natural numbers is N(N+1)/2. We can add all the numbers in the array. That should be of order n. Then we subtract that from the previous sum and that is the number.
