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.

C

Download   Run Code

Java

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

avatar
  Subscribe  
newest oldest most voted
Notify of
Akash KAndpal
Guest

Well explained …. A simple application of Binary Search 🙂

narendra singh bagdwal
Guest
narendra singh bagdwal

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

Claudio
Guest

There is the assumption that there is a single missing term.
You know the step s of the sequence (you can find it in constant time checking the first 4 terms). Now you basically know what value every element should have if there was no missing term: a[i]=s*i+a[0], so you can check the mid term, if it is not equal to this number then it means that the missing term is at its left, otherwise it is at its right.