Problem Description

You are given an array arr that was originally an arithmetic progression (arithmetic sequence). In an arithmetic progression, the difference between consecutive elements is always the same. This means arr[i + 1] - arr[i] has the same value for all valid indices i.

From this arithmetic progression, exactly one value was removed. The removed value was not the first element and not the last element of the original sequence.

Your task is to find and return the value that was removed.

For example:

• If the original arithmetic progression was [1, 3, 5, 7, 9] and the value 5 was removed, you would receive arr = [1, 3, 7, 9]
• You need to determine that 5 is missing and return it

The solution uses the arithmetic series sum formula. For an arithmetic sequence with n terms, first term a₁, and last term aₙ, the sum is (a₁ + aₙ) × n / 2. Since one element is missing from the middle, the original sequence had len(arr) + 1 terms. The missing number equals the expected sum minus the actual sum of the given array.

Intuition

When we have an arithmetic progression with one missing element, we can leverage a key insight: the first and last elements of the array remain unchanged (since the problem guarantees the removed element wasn't at either end).

Think about what information we still have:

1. The first term of the original sequence: arr[0]
2. The last term of the original sequence: arr[-1]
3. The original sequence had len(arr) + 1 terms (current length plus the one removed)

In any arithmetic progression, if we know the first term, last term, and number of terms, we can calculate the total sum using the formula sum = (first + last) × count / 2. This works because in an arithmetic sequence, the average of all terms equals the average of the first and last terms.

So we can calculate what the sum SHOULD have been for the complete sequence: (arr[0] + arr[-1]) × (len(arr) + 1) / 2

We can also calculate what the sum ACTUALLY is by adding up all current elements: sum(arr)

The difference between these two values must be exactly the missing number! This is because:

• Expected sum = sum of all original numbers
• Actual sum = sum of all numbers except the missing one
• Therefore: Missing number = Expected sum - Actual sum

This approach is elegant because it doesn't require us to figure out the common difference or iterate through the array to find where the gap is. We just need these two sums.

Learn more about Math patterns.

Solution Approach

The implementation directly applies the arithmetic series sum formula to find the missing number.

Step 1: Calculate the expected sum of the complete arithmetic progression

Using the formula sum = (first + last) × n / 2, where:

• First term: arr[0]
• Last term: arr[-1]
• Number of terms in original sequence: len(arr) + 1 (current length plus the removed element)

Expected sum = (arr[0] + arr[-1]) * (len(arr) + 1) // 2

Step 2: Calculate the actual sum of the given array

Actual sum = sum(arr)

Step 3: Find the missing number

Missing number = Expected sum - Actual sum

The complete implementation in one line:

return (arr[0] + arr[-1]) * (len(arr) + 1) // 2 - sum(arr)

Why this works:

• The arithmetic series sum formula gives us what the total should be if no element was missing
• The sum(arr) function gives us the actual total of the current array
• The difference between these two values is exactly the missing element

Time Complexity: O(n) where n is the length of the array, due to the sum() function iterating through all elements.

Space Complexity: O(1) as we only use a constant amount of extra space for the calculation.

Note: We use integer division // to ensure the result is an integer, which is appropriate since we're dealing with arithmetic progressions of integers.

Example Walkthrough

Let's walk through a concrete example to see how this solution works.

Given array: arr = [5, 7, 11, 13]

We know one number was removed from the middle of an arithmetic progression. Let's find it using our solution approach.

Step 1: Calculate the expected sum of the complete sequence

The original sequence had len(arr) + 1 = 4 + 1 = 5 terms.

Using the arithmetic series sum formula:

• First term: arr[0] = 5
• Last term: arr[-1] = 13
• Number of terms: 5

Expected sum = (5 + 13) × 5 / 2 = 18 × 5 / 2 = 90 / 2 = 45

Step 2: Calculate the actual sum of the given array

Actual sum = 5 + 7 + 11 + 13 = 36

Step 3: Find the missing number

Missing number = Expected sum - Actual sum = 45 - 36 = 9

Verification: The original arithmetic progression was [5, 7, 9, 11, 13] with a common difference of 2. When 9 was removed, we got [5, 7, 11, 13]. Our formula correctly identified that 9 is the missing value!

The beauty of this approach is that we never needed to figure out the common difference (which was 2) or search for where the gap occurred. The mathematical relationship between the sum formulas gave us the answer directly.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array. This is because the sum(arr) function iterates through all elements in the array once to calculate their sum. The other operations - accessing arr[0], arr[-1], len(arr), and performing arithmetic operations - all take O(1) time.

The space complexity is O(1). The algorithm only uses a constant amount of extra space for storing intermediate calculation results (the sum and arithmetic operations), regardless of the input array size. No additional data structures are created that scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Assuming the Common Difference is Always Positive

The Problem: The solution assumes that we can always use the arithmetic sum formula with just the first and last elements. However, this approach fails when the arithmetic progression has a common difference of 0 (all elements are the same).

Example:

• Original sequence: [5, 5, 5, 5, 5]
• After removing one element: [5, 5, 5, 5]
• Expected sum: (5 + 5) * 5 // 2 = 25
• Actual sum: 20
• Result: 5 (correct, but only by coincidence)

The Real Issue: When all elements are identical, removing any middle element produces the same result. The problem statement should clarify that the common difference is non-zero, or we need to handle this edge case explicitly.

Pitfall 2: Not Handling Small Arrays Correctly

The Problem: The solution might not work correctly for very small arrays (length 2 or 3) where determining the common difference becomes ambiguous.

Example:

• Given array: [1, 7]
• Could be from: [1, 3, 5, 7] (missing 3 or 5) or [1, 4, 7] (missing 4)
• The formula gives: (1 + 7) * 3 // 2 - 8 = 12 - 8 = 4

Solution: For small arrays, we need to determine the common difference first:

def missingNumber(self, arr: List[int]) -> int:
    n = len(arr)
  
    # For arrays of length 2, we need special handling
    if n == 2:
        # The missing element is the middle of the arithmetic sequence
        return (arr[0] + arr[1]) // 2
  
    # Determine the common difference
    # Check the first three and last three elements to find the actual difference
    diff1 = arr[1] - arr[0]
    diff2 = arr[2] - arr[1]
    diff3 = arr[-1] - arr[-2]
  
    # The common difference is the one that appears more frequently
    # or the smaller absolute value if one is double the other
    if diff1 == diff2 or diff1 == diff3:
        common_diff = diff1
    elif diff2 == diff3:
        common_diff = diff2
    elif abs(diff1) == 2 * abs(diff2):
        common_diff = diff2
    elif abs(diff2) == 2 * abs(diff1):
        common_diff = diff1
    else:
        common_diff = diff3
  
    # Now find the missing element by checking consecutive differences
    for i in range(len(arr) - 1):
        if arr[i + 1] - arr[i] != common_diff:
            return arr[i] + common_diff
  
    # Fallback to the original formula (shouldn't reach here)
    return (arr[0] + arr[-1]) * (len(arr) + 1) // 2 - sum(arr)

Pitfall 3: Integer Overflow for Large Numbers

The Problem: When dealing with very large numbers, the multiplication (arr[0] + arr[-1]) * (len(arr) + 1) might cause integer overflow in languages with fixed integer sizes.

Solution: In Python, this is generally not an issue due to arbitrary precision integers. However, for other languages or when precision is critical, rearrange the formula to minimize intermediate values:

def missingNumber(self, arr: List[int]) -> int:
    # Alternative calculation to avoid large intermediate values
    n = len(arr) + 1
  
    # Calculate sum using the formula but with rearranged operations
    if n % 2 == 0:
        expected_sum = (arr[0] + arr[-1]) * (n // 2)
    else:
        expected_sum = ((arr[0] + arr[-1]) // 2) * n + (arr[0] + arr[-1]) % 2 * n // 2
  
    return expected_sum - sum(arr)