💬 Discord
Sign In
NeetCode #266LC-1228EasyBinary SearchNC Algo100
← Back to All Problems

#266 · #1228 · Missing Number In Arithmetic Progression(等差子数组中的缺失数字)

📌 Problem Statement & Constraints

Given an array arr that was originally an arithmetic progression with a missing element, return the missing value. The progression has at least 3 elements and the common difference is non-zero. Constraints: 3 <= arr.length <= 1000, 0 <= arr[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. The common difference is (arr[-1] - arr[0]) / n, where n is the length of the array (the original progression had n + 1 terms).
  2. Then compare each element with its expected value arr[0] + i * d and return the first mismatch's expected value.
  3. Because only one element is missing, at most one mismatch can occur before the gap.
  4. A binary search version compares arr[mid] with the expected value to decide which side contains the gap -- O(log n).

💻 Benchmark Python3 Implementation

class Solution:
    def missingNumber(self, arr: List[int]) -> int:
        n = len(arr)
        d = (arr[-1] - arr[0]) // n    # the original progression had n+1 terms
        for i in range(1, n):
            expected = arr[0] + i * d
            if arr[i] != expected:
                return expected
        return arr[0]                  # unreachable per the problem guarantee


# Binary-search variant: O(log n)
class Solution2:
    def missingNumber(self, arr: List[int]) -> int:
        n = len(arr)
        d = (arr[-1] - arr[0]) // n
        lo, hi = 0, n - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if arr[mid] == arr[0] + mid * d:
                lo = mid + 1           # gap is to the right
            else:
                hi = mid
        return arr[0] + lo * d

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) for the linear scan, O(log n) for the binary-search variant.
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Dividing by n - 1 instead of n: with one element missing, the array has n elements but the progression has n + 1 terms, so the divisor is n.
  • Using floating-point division: d is always an integer here (the problem guarantees a valid progression), so integer division is exact.
  • Returning arr[i] instead of the expected value: the missing element is the expected value, not the array's element.
  • Assuming the gap is at the end: it can be anywhere, so the scan must check every position.