Find Missing Number - Algorithms and Problem SolvingAlgorithms and Problem Solving

Find Missing Number - Algorithms and Problem SolvingAlgorithms and Problem Solving

1. Given a set of positive numbers less than equal to N, where one number is missing. Find the missing number efficiently.
2. Given a set of positive numbers less than equal to N, where two numbers are missing. Find the missing numbers efficiently.
3. Given a sequence of positive numbers less than equal to N, where one number is repeated and another is missing. Find the repeated and the missing numbers efficiently.
4. Given a sequence of integers (positive and negative). Find the first missing positive number in the sequence.

Solutions should not use no more than O(n) time and constant space.

For example,

1. A=[2,1,5,8,6,7,3,10,9] and N=10 then, 4 is missing.
2. A=[2,1,5,8,6,7,3,9] and N=10 then, 4 and 10 are missing.
3. A=[2,1,5,8,3,6,7,3,10] and N=10 then, 3 is repeating and 9 is missing.
2. A=[1,2,0] then first missing positive is 3, A=[3,4,-1,1], the first missing positive is 2.

Single Number Missing
A trivial approach would be to sort the array and loop through zero to N-1 to check whether index i contains number i+1. This will take constant space but takes O(nlgn) time. We can do a counting sort to sort the array but still it'll take in O(n+k) time and O(k) space. But we need to do it O(n) time and constant space, how?

Its rather simple to do it if we apply some elementary mathematics. We know that the input set contains positive numbers less than equal to N. If there were no missing in the sequence then summation of all the numbers would yield a sum of N*(N+1)/2 , which is the value of summation of numbers 1 to N. But if one number is missing then the summation of the given numbers, S will be less than expected sum N*(N+1)/2 and the difference (N*(N+1)/2 – S) is the missing number. This is O(n) time and O(1) space algorithm.

Read full article from Find Missing Number - Algorithms and Problem SolvingAlgorithms and Problem Solving