Find the missing number in Arithmetic Progression

Given an array arr of n elements that represents an Arithmetic Progression having one missing element in the order, find that missing element.

Example: Input: arr = [1,2,3,4,6]
Output: Missing element is 5.

Input: arr = [3,6,12,15]
Output: Missing element is 9.

The common difference d of the Arithmetic Progression having exactly one missing element can be calculated as $d = \frac{(arr[n-1] - arr[0])}{n}$, assuming that the common difference is always an integer.

Simple Solution:

The simple solution is to iterate over all the elements of the array and check if the difference between the current element and the next element is equal to d or not.

missingElement(int arr[], int d)
{ // iterate over all the elements except the last element.
    for (int i = 0; i < arr.length - 1; i++)
    {
        // if the difference between the current and the next element is not equal to d, then return the answer as current element + d.
        if (arr[i + 1] - arr[i] != d)
        {
            return arr[i] + d;
        }
    }
}

The time complexity of the above approach is O(n), where n is the number of elements in the array.

Using Binary Search

Every time we go to the middle element and decide our next move based on the following cases.

Case 1: Check if the difference between arr[mid] and arr[next=mid+1] element is not d, then the missing element is arr[mid] + d.

Case 2: Check if the difference between arr[mid] and arr[previous=mid-1] element is not d, then the missing element is arr[mid-1] + d.

Now if both the above cases fail, we can conclude that the missing element is neither immediately before or after the current mid element. So, it can be either in the left half from low to mid-1 or in the right half from mid+1 to high. Therefore, we will proceed to further cases.

Case 3: Check if all the elements in the left half follow the Arithmetic Progression (Conversely, the missing element is not in the left half). For that, we need to check if the arr[mid] element is the desired mid element using the formula to find nth term in AP i.e. ($first term + (n - 1) * difference$). In our case, the formula can be rewritten as arr[0] + (mid*d) and this should be equal to arr[mid]. If so, we can say that the missing element lies in the right half.

Case 4: If the case 3 condition fails, then we can conclude that the missing element lies in the left half.

Until one of the cases among 1 and 2 does not pass, we repeat the above cycle.

The time complexity of the binary search approach is $O(logn)$.

• C++
• Python
• Java

#include <stdio.h>
#include <limits.h>

int missingElementAP(int arr[], int n)
{

    // Common Difference
    int d = (arr[n - 1] - arr[0]) / n;
    int low = 0;
    int high = n - 1;

    while (low < high)
    {
        // Find the middle index
        int mid = low + (high - low) / 2;

        // if mid and the immediate next element to mid are not in AP, then missing element is arr[mid] + d.
        if (arr[mid + 1] - arr[mid] != d)
            return arr[mid] + d;

        // if mid and the immediate previous element to mid are not in AP, then missing element is arr[mid-1] + d.
        if (mid > 0 && arr[mid] - arr[mid - 1] != d)
            return arr[mid - 1] + d;

        // if elements of the left half are in AP, then missing element is in right half.
        if (arr[mid] == arr[0] + mid * d)
            low = mid + 1;

        // else missing element is in the left half.
        else
            high = mid - 1;
    }
    // Invalid Input
    return INT_MAX;
}

def missingElementAP(arr, n):
    # Common Difference
    d = (arr[n - 1] - arr[0]) // n
    low = 0
    high = n - 1
    while low < high:
        # Finding the middle index
        mid = int(low + (high - low) / 2)

        # if mid and the immediate next element to mid are not in AP, then missing element is arr[mid] + d.
        if arr[mid + 1] - arr[mid] != d:
            return arr[mid] + d

        # if mid and the immediate previous element to mid are not in AP, then missing element is arr[mid-1] + d.
        if mid > 0 and arr[mid] - arr[mid - 1] != d:
            return arr[mid - 1] + d

        # if elements of the left half are in AP, then the missing element is in the right half.
        if arr[mid] == arr[0] + mid * d:
            low = mid + 1

        # else the missing element is in the left half.
        else:
            high = mid - 1
    return "invalid"

static int missingElementAP(int arr[], int n) {
  // Common Difference
  int d = (arr[n - 1] - arr[0]) / n;
  int low = 0;
  int high = n - 1;

  while (low < high) {
    // Find the middle index
    int mid = low + (high - low) / 2;

    // if mid and the immediate next element to mid are not in AP, then missing
    // element is arr[mid] + d.
    if (arr[mid + 1] - arr[mid] != d)
      return arr[mid] + d;

    // if mid and the immediate previous element to mid are not in AP, then missing
    // element is arr[mid-1] + d.
    if (mid > 0 && arr[mid] - arr[mid - 1] != d)
      return arr[mid - 1] + d;

    // if elements of the left half are in AP, then missing element is in right
    // half.
    if (arr[mid] == arr[0] + mid * d)
      low = mid + 1;

    // else missing element is in the left half.
    else
      high = mid - 1;
  }

  // Invalid Input
  return Integer.MAX_VALUE;
}