Missing Number In Arithmetic Progression

Easy · Math & Geometry · Explanation and code example

Binary Search

How it works

Since the array is sorted and follows an arithmetic progression, we can use binary search to locate the missing element faster. At any index i, the expected value is arr[0] + i * difference. If the actual value matches, all elements up to that index are correct, so the missing number is to the right. If there is a mismatch, the missing number is at or before that index. This allows us to narrow down the search space logarithmically.

Steps

  1. Calculate the common difference: difference = (arr[n - 1] - arr[0]) / n.
  2. Initialize lo = 0 and hi = n - 1.
  3. While lo < hi:
    • Compute mid = (lo + hi) / 2.
    • If arr[mid] equals the expected value arr[0] + mid * difference, the missing element is after mid, so set lo = mid + 1.
    • Otherwise, the missing element is at or before mid, so set hi = mid.
  4. Return arr[0] + difference * lo as the missing number that should be at index lo.

Complexity

  • Time complexity: O(log n)
  • Space complexity: O(1) constant space

Where n is the length of array arr.

Things to watch for

Incorrect Common Difference Calculation

The common difference must be calculated as (arr[n-1] - arr[0]) / n, not (arr[n-1] - arr[0]) / (n-1). Since one element is missing, the full sequence would have n+1 elements with n gaps, making the divisor n.

Not Handling Zero Difference

When the common difference is zero (all elements are the same), any position could be the "missing" element since the missing value equals all existing values. The linear search returns the first element in this case, which is correct.

Integer Division Truncation

In languages where division truncates toward zero, negative arithmetic progressions may produce incorrect common differences. Ensure the division correctly handles both positive and negative sequences.

Python code example

from typing import List

class Solution:
    def missingNumber(self, arr: List[int]) -> int:
        n = len(arr)

        # Get the difference `difference`.
        difference = (arr[n - 1] - arr[0]) // n

        lo = 0
        hi = n - 1

        # Basic binary search template.
        while lo < hi:
            mid = (lo + hi) // 2

            # All numbers up to `mid` have no missing number, so search on the right side.
            if arr[mid] == arr[0] + mid * difference:
                lo = mid + 1

            # A number is missing before `mid` inclusive of `mid` itself.
            else:
                hi = mid

        # Index `lo` will be the position with the first incorrect number.
        # Return the value that was supposed to be at this index.
        return arr[0] + difference * lo

C++ code example

class Solution {
public:
    int missingNumber(vector<int> &arr) {
        int n = arr.size();

        // Get the difference `difference`.
        int difference = (arr.back() - arr.front()) / n;
        int lo = 0;
        int hi = n - 1;

        // Basic binary search template.
        while (lo < hi) {

            int mid = (lo + hi) / 2; // Note: int mid = lo + (hi - lo) / 2; is recommended to avoid potential overflow
            // All numbers upto `mid` have no missing number, so search on the right side.
            if (arr[mid] == arr.front() + mid * difference) {
                lo = mid + 1;
            }

            // A number is missing before `mid` inclusive of `mid` itself.
            else {
                hi = mid;
            }
        }

        // Index `lo` will be the position with the first incorrect number.
        // Return the value that was supposed to be at this index.
        return arr.front() + difference * lo;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations