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

## Java

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).     (2 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest
Akash KAndpal

Well explained …. A simple application of Binary Search 🙂 Guest
narendra singh bagdwal

How do you know that the missing number is on left or right of the mid element. 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, 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.