Problem Description

You are given a list of n numbers that form an arithmetic progression except for one missing number. The numbers are sorted in strictly increasing order and exactly one number from the progression is missing from the list. Your task is to find and return the missing number.

• There is exactly one valid solution for each input.
• The input is an integer array arr of length n (where n >= 3).
• Do not reuse elements or assume duplicates.
• The difference between any two consecutive elements (except where the missing number is) is constant.

For example, given arr = [5, 7, 11, 13], the missing number is 9 because the arithmetic progression should be 5, 7, 9, 11, 13.

Thought Process

At first glance, you might think to check every possible number between the first and last elements to see which is missing. However, since the numbers form an arithmetic progression, we can use the properties of such sequences to find the missing number more efficiently.

• Brute-force: Generate the full arithmetic sequence, then compare with the input to find the missing number. This works, but it's not efficient.
• Optimized approach: Use the fact that the difference between elements should be constant. If we can determine the common difference (step) and find where this pattern is broken, we can directly identify the missing number.

The key insight is that the "jump" between two adjacent numbers will be larger at the point where the missing number would have been.

Solution Approach

Let's break down the optimized solution step-by-step:

1. Calculate the common difference:
   Since one number is missing, the actual difference between the first and last elements divided by the length of the array gives the intended step size. That is, diff = (arr[-1] - arr[0]) // len(arr).
2. Scan for the anomaly:
   Iterate through the array, and for each pair of consecutive elements, check if their difference equals diff. If not, the missing number is between these two elements.
3. Return the missing number:
   The missing number is simply arr[i] + diff where the anomaly is found.

This approach is efficient and leverages the properties of arithmetic progressions to avoid unnecessary computation.

Example Walkthrough

Let's walk through an example with arr = [5, 7, 11, 13]:

1. Compute the common difference:
   diff = (13 - 5) // 4 = 8 // 4 = 2
2. Check differences:
   • Between 5 and 7: 7 - 5 = 2 (OK)
   • Between 7 and 11: 11 - 7 = 4 (Not OK)
3. Missing number is: 7 + 2 = 9
4. Check remaining pairs:
   • Between 11 and 13: 13 - 11 = 2 (OK)

So, the missing number is 9.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n) to generate the full sequence and compare with input.
  • Space Complexity: O(n) for the generated sequence.
• Optimized approach:
  • Time Complexity: O(n) — we scan the array once.
  • Space Complexity: O(1) — we only use a few variables for calculation.

The optimized solution is clearly better in both time and space, especially for large arrays.

Summary

By leveraging the properties of arithmetic progressions, we can efficiently find the missing number by:

• Calculating the expected common difference
• Scanning for where the difference deviates
• Returning the number that should have been there

This solution is elegant because it avoids unnecessary computation and uses mathematical reasoning to solve the problem in linear time and constant space.

Code Implementation

class Solution:
    def missingNumber(self, arr):
        n = len(arr)
        diff = (arr[-1] - arr[0]) // n
        for i in range(n - 1):
            if arr[i + 1] - arr[i] != diff:
                return arr[i] + diff
        # If not found in loop, missing number is at the end or start
        return arr[0] + diff
      

class Solution {
public:
    int missingNumber(vector<int>& arr) {
        int n = arr.size();
        int diff = (arr[n - 1] - arr[0]) / n;
        for (int i = 0; i < n - 1; ++i) {
            if (arr[i + 1] - arr[i] != diff) {
                return arr[i] + diff;
            }
        }
        // If not found in loop
        return arr[0] + diff;
    }
};
      

class Solution {
    public int missingNumber(int[] arr) {
        int n = arr.length;
        int diff = (arr[n - 1] - arr[0]) / n;
        for (int i = 0; i < n - 1; i++) {
            if (arr[i + 1] - arr[i] != diff) {
                return arr[i] + diff;
            }
        }
        // If not found in loop
        return arr[0] + diff;
    }
}
      

var missingNumber = function(arr) {
    const n = arr.length;
    const diff = Math.floor((arr[n - 1] - arr[0]) / n);
    for (let i = 0; i < n - 1; i++) {
        if (arr[i + 1] - arr[i] !== diff) {
            return arr[i] + diff;
        }
    }
    // If not found in loop
    return arr[0] + diff;
};