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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <stdio.h> // Function to find missing term in a sequence int missingTerm(int A[], int n) { // search space is A[low..high] int low = 0, high = n - 1; // calculate common difference between successive elements int d = (A[n - 1] - A[0]) / n; // run till search space is exhausted while (low <= high) { // find middle index int mid = high - (high - low) / 2; // check difference of mid element with its right neighbor if (mid + 1 < n && A[mid + 1] - A[mid] != d) return A[mid + 1] - d; // check difference of mid element with its left neighbor if (mid - 1 >= 0 && A[mid] - A[mid - 1] != d) return A[mid - 1] + d; // if missing element lies on left sub-array, then we reduce // our search space to left sub-array A[low..mid-1] if (A[mid] - A[0] != (mid - 0) * d) high = mid - 1; // if missing element lies on right sub-array, then reduce // our search space to right sub-array A[mid+1..high] else low = mid + 1; } } // Find missing term in a sequence int main(void) { int A[] = { 5, 7, 9, 11, 15 }; int n = sizeof(A) / sizeof(A[0]); printf("Missing element is %d", missingTerm(A, n)); return 0; } |

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
class Search { // Function to find missing term in a sequence public static int missingTerm(int[] A) { // search space is A[left..right] int left = 0, right = A.length - 1; // calculate common difference between successive elements int diff = (A[A.length - 1] - A[0]) / A.length; // run till search space is exhausted while (left <= right) { // find middle index int mid = right - (right - left) / 2; // check difference of mid element with its right neighbor if (mid + 1 < A.length && A[mid + 1] - A[mid] != diff) { return A[mid + 1] - diff; } // check difference of mid element with its left neighbor if (mid - 1 >= 0 && A[mid] - A[mid - 1] != diff) { return A[mid - 1] + diff; } // if missing element lies on left sub-array, then we reduce // our search space to right sub-array A[left..mid-1] if (A[mid] - A[0] != (mid - 0) * diff) { right = mid - 1; } // if missing element lies on right sub-array, then reduce // our search space to right sub-array A[mid+1..right] else { left = mid + 1; } } return -1; } public static void main(String[] args) { int[] A = { 5, 7, 9, 11, 15 }; System.out.println("Missing element is " + missingTerm(A)); } } |

`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

Well explained …. A simple application of Binary Search 🙂

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

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.