Missing Number In Arithmetic Progression

easy math arithmetic progression sum formula

Problem

In an array of integers arr, the values form an arithmetic progression (consecutive elements share a constant difference). Exactly one value has been removed from somewhere in the middle — never the first or last element. Return that missing value.

Inputarr = [5, 7, 11, 13]

Output9

The full progression is 5, 7, 9, 11, 13 with common difference 2; the missing value is 9.

arr (comma-separated)

def missing_number(arr):
    n = len(arr)
    expected = (arr[0] + arr[-1]) * (n + 1) // 2
    actual = sum(arr)
    return expected - actual

function missingNumber(arr) {
  const n = arr.length;
  const expected = (arr[0] + arr[n - 1]) * (n + 1) / 2;
  let actual = 0;
  for (const x of arr) actual += x;
  return expected - actual;
}

class Solution {
    public int missingNumber(int[] arr) {
        int n = arr.length;
        int expected = (arr[0] + arr[n - 1]) * (n + 1) / 2;
        int actual = 0;
        for (int x : arr) actual += x;
        return expected - actual;
    }
}

int missingNumber(vector<int>& arr) {
    int n = arr.size();
    int expected = (arr[0] + arr[n - 1]) * (n + 1) / 2;
    int actual = 0;
    for (int x : arr) actual += x;
    return expected - actual;
}

Explanation

Because exactly one interior value was removed, the array we get is a complete arithmetic progression minus one number. The neat trick is to compute what the full sum should be and subtract what we actually have.

The full progression has n + 1 terms (the n we see plus the missing one), and crucially the first and last values are unchanged since only a middle element was dropped.

The sum of an arithmetic series is (first + last) * count / 2, so the expected total is (arr[0] + arr[-1]) * (n + 1) / 2. We then add up the actual elements with sum(arr).

The difference expected - actual is exactly the one value that is missing, found in a single pass with no extra memory.

Example: [5, 7, 11, 13] has n = 4, so expected = (5 + 13) * 5 / 2 = 45. The actual sum is 36, so the missing value is 45 - 36 = 9.

Time: O(n) Space: O(1)