Find Missing Term in a Sequence in log(n) time

Given a sequence of numbers such that the difference between the consecutive terms is constant, find missing term in it in O(log(n)) time.


For example,

Input:  Sequence is [5, 7, 9, 11, 15]
Output: Missing term is 13

Input:  Sequence is [1, 4, 7, 13, 16]
Output: Missing term is 10


A simple solution would be to run a linear search on the array and find the missing element by comparing difference of adjacent elements of the array with the common difference of the sequence. We can find the common difference between successive elements of the sequence by using formula –

common difference = (last element in sequence – first element in sequence) / n

Here n is the total number of elements in sequence. The problem with this approach is that its worst case time complexity is O(n). This solution also do not take advantage of the fact that the input is sorted in ascending or descending order.

Whenever we’re asked to perform a search on a sorted array, we should always think of binary search algorithm. We can easily solve this problem in O(log(n)) time by modifying binary search algorithm. The idea is to check the difference of mid element with its left and right neighbor. If the difference is not equal to the common difference then we know that missing number lies between mid and its left or right neighbor. If the difference is same as common difference of the sequence, then we reduce our search space to left sub-array A[low..mid-1] or right sub-array A[mid+1..high] depending upon if missing element lies on left sub-array or not.


Download   Run Code


Download   Run Code


Missing term is 13

The time complexity of above solution is O(log(n)) and auxiliary space used by the program is O(1).

Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Get great deals at Amazon

Leave a Reply

newest oldest most voted
Notify of
Akash KAndpal
Akash KAndpal

Well explained …. A simple application of Binary Search 🙂

narendra singh bagdwal
narendra singh bagdwal

How do you know that the missing number is on left or right of the mid element.