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 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. 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.

C++

Download   Run Code

Output:

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 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Akash KAndpal
Guest
Akash KAndpal

Well explained …. A simple application of Binary Search 🙂

wpDiscuz