Domain 1EasyCORE

Missing Number In Arithmetic Progression

The problem asks us to find the missing number in an arithmetic progression array where one element has been removed. The input is an array `arr` of integers, and the output should be the integer that was removed. The constraints are that the array length is between 3 and 1000, and each element is between 0 and 10^5.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math

1228. Missing Number In Arithmetic Progression

Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 0
Acceptance rate: 51.0%


Problem Breakdown

The problem asks us to find the missing number in an arithmetic progression array where one element has been removed. The input is an array arr of integers, and the output should be the integer that was removed. The constraints are that the array length is between 3 and 1000, and each element is between 0 and 10^5.

Inputs:

  • An array arr of integers representing an arithmetic progression with one missing number.

Outputs:

  • An integer representing the missing number in the original arithmetic progression.

Implicit Constraints:

  • The first and last elements are not removed.
  • The array is guaranteed to have at least three elements, ensuring that there’s enough information to determine the common difference.

Intuition

A brute-force approach would involve generating all possible numbers in the range from the first to the last element of the array and checking which one is missing. However, this approach is inefficient with a time complexity of O(n^2) due to nested loops.

The key insight is that in an arithmetic progression, the difference between consecutive elements is constant. We can use this property to find the common difference by calculating the total expected sum of the array if no number was missing and comparing it to the actual sum of the given array. The difference between these sums will be the missing number.

Approach

  1. Calculate the common difference d using the formula: d = (arr[-1] - arr[0]) // len(arr).
  2. Compute the expected sum of the arithmetic progression if no number was missing.
  3. Subtract the actual sum of the array from this expected sum to find the missing number.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the array. We need to iterate through the array to calculate the actual sum.
  • Space Complexity: O(1), as we only use a few extra variables for calculations.

Solution

def missingNumber(arr):
    # Calculate the common difference
    d = (arr[-1] - arr[0]) // len(arr)
    
    # Calculate the expected sum of the arithmetic progression
    expected_sum = (len(arr) + 1) * (arr[0] + arr[-1]) // 2
    
    # Calculate the actual sum of the array
    actual_sum = sum(arr)
    
    # The missing number is the difference between the expected and actual sums
    return expected_sum - actual_sum

# Example usage:
print(missingNumber([5, 7, 11, 13]))  # Output: 9
print(missingNumber([15, 13, 12]))     # Output: 14

Edge Cases Handled

  • Common Difference of Zero: If the common difference is zero (i.e., all elements are the same), the expected sum will be equal to the actual sum, and thus the missing number will be the same as any element in the array.
  • Single Missing Element: The approach correctly identifies a single missing element between the first and last elements of the array.