Searching and Sorting: Find the missing number in Arithmetic Progression

Problem Statement:

You are given an array that has elements of arithmetic progression in order.

One element is missing, you need to find that

Example

Input: arr[] = {2, 4, 6, 10, 12, 14}
Output: 8

Solution

This problem can be solved in number of different methods.

Method 1:

You can traverse the array linearly and then find the missing element.

Here the time complexity is O(n)

Method 2:

We use Binary Search in this method.

We goto the middle element and check if the difference between missing element and the next element is equal to the diff or not.

If not, then the missing element lies between mid and mid+1.

Then if the middle element is equal to n/2th term in AP series, then missing element lies in right half, else left half.

Time Complexity O(logn)

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;

int find_missing_number(int arr[], int low, int high, int diff) 
{ 
    if (high <= low) 
        return INT_MAX; 
  
    int mid = low + (high - low) / 2; 
  

    if (arr[mid + 1] - arr[mid] != diff) 
        return (arr[mid] + diff); 
  
    if (mid > 0 && arr[mid] - arr[mid - 1] != diff) 
        return (arr[mid - 1] + diff); 
  

    if (arr[mid] == arr[0] + mid * diff) 
        return find_missing_number(arr, mid + 1,  
                               high, diff); 
  
    return find_missing_number(arr, low, mid - 1, diff); 
} 

int main() 
{ 
    int arr[] = {2, 4, 8, 10, 12, 14}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int diff = (arr[n - 1] - arr[0]) / n; 

    cout << "The missing element is " << find_missing_number(arr, 0, n - 1, diff)<<endl; 

    return 0; 
}  

Output:

The missing element is 6