Finding Missing Number in an Increasing Sequence

Problem Statement

You are given an array which contains an increasing sequence of numbers from 1 to N. There is one number missing in the sequence. The task at hand is find the missing number in minimum running time.

Input: An array A of numbers in increasing order, with one number missing.

Output: The missing integer

Constraint: The sequence is strictly increasing. The algorithm should finish in minimum time.

Approach for Finding Missing Number

At first, it looks like a simple problem which can be solved in O(N) time. Indeed it is. Here are the steps:

  • Start traversing from the beginning of the array (assuming the array index starts from 1)
  • The sequence starts from 1 and ends in N, so at any index i either of the two cases happen:
    • A[i] contains a number equal to i
    • A[i] contains a number greater than i
  • Break from the loop at the first index where A[i] >  i
  • The missing number is i

Finding Missing Number

When we run through the above algorithm and the array index starts at 1, then at index 7 A[7] > 7. Hence the missing number is 7

That was really easy but the running time gets proportional to N, where N is the size of the array.

Can we do better?

Let us try. After thinking for a while, it strikes that the sequence is sorted in increasing order. Hence, we can easily use Binary Search and narrow down our search space by half after every comparison.

So, what should be the comparison expression in the binary search expression?

Surprisingly it should be same as the one in previous approach. Here are the steps:

  • Initialize two pointers start = 1 and end = A.length
  • Calculate the mid of start and end.
  • Evaluate the number A[mid]. Two cases arise:
    • A[mid] == mid
    • A[mid] > mid
  • If A[mid] == mid
    • position start to mid
  • If A[mid] > mid
    • position end to mid
  • Repeat till end-start > 1
  • The missing element is A[mid]+1

Source Code for Finding Missing Number

Here is the link for the complete code.

Conclusion

We learnt that we must evaluate and reconsider each information given in a problem statement before jumping to a solution. The moment we find out that the array is sorted, it becomes very easy to deduce that we need Binary Search.

Thinking out of the box is important, we have always learnt that Binary Search is used to find a given number, so it is less likely that we will ever try to use it when the number is not given, as it is in this case.