Solution Explanation for Missing Number in Arithmetic Progression

This problem asks to find the missing number in an arithmetic progression (AP) array where one number has been removed. The array is guaranteed to be a valid AP with only one number missing, and the missing number is not the first or last element.

We can solve this using two main approaches:

Approach 1: Using the Arithmetic Series Sum Formula

This approach leverages the formula for the sum of an arithmetic series: S = n/2 * (a + l), where n is the number of terms, a is the first term, and l is the last term.

1. Calculate the expected sum: If the missing number were present, the number of terms n would be len(arr) + 1. We can calculate the expected sum S using the formula with n = len(arr) + 1, a = arr[0], and l = arr[-1].

2. Calculate the actual sum: Sum all the elements present in the input array arr.

3. Find the difference: The difference between the expected sum and the actual sum is the missing number.

Time Complexity: O(n) due to the single iteration to calculate the sum of the array. Space Complexity: O(1) as we use only a few variables to store intermediate values.

Approach 2: Find Common Difference and Traverse

This approach identifies the common difference and then iterates to find the missing element.

1. Calculate the common difference: The common difference d in an AP is calculated as (last term - first term) / (number of terms - 1). Here, d = (arr[-1] - arr[0]) / len(arr)

2. Iterate and compare: Iterate through the array, comparing consecutive elements. If the difference between consecutive elements is not equal to d, the missing number is the expected value based on the previous element and d.

3. Handle edge cases: If the loop completes without finding a missing number, it implies that all numbers are identical. In such cases, return the first element of the array.

Time Complexity: O(n) due to the single iteration through the array. Space Complexity: O(1) as only a few variables are used.

Code Implementations

Here's the code in multiple programming languages for both approaches: (Note: Approach 1 is generally more concise and efficient).

Approach 1 (Arithmetic Series Sum Formula):

Python:

class Solution:
    def missingNumber(self, arr: List[int]) -> int:
        n = len(arr)
        expected_sum = (arr[0] + arr[-1]) * (n + 1) // 2  # Integer division
        actual_sum = sum(arr)
        return expected_sum - actual_sum

Java:

class Solution {
    public int missingNumber(int[] arr) {
        int n = arr.length;
        long expectedSum = (long)(arr[0] + arr[n - 1]) * (n + 1) / 2; // Avoid integer overflow
        long actualSum = 0;
        for (int num : arr) {
            actualSum += num;
        }
        return (int)(expectedSum - actualSum);
    }
}

C++:

class Solution {
public:
    int missingNumber(vector<int>& arr) {
        long long n = arr.size();
        long long expectedSum = (long long)(arr[0] + arr[n - 1]) * (n + 1) / 2;
        long long actualSum = accumulate(arr.begin(), arr.end(), 0LL);
        return expectedSum - actualSum;
    }
};

Approach 2 (Find Common Difference and Traverse):

Python:

class Solution:
    def missingNumber(self, arr: List[int]) -> int:
        n = len(arr)
        d = (arr[-1] - arr[0]) // n
        for i in range(1, n):
            if arr[i] != arr[i - 1] + d:
                return arr[i - 1] + d
        return arr[0]

Java:

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

C++:

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

These examples demonstrate the core logic for both approaches in different languages. Remember to handle potential integer overflow issues, particularly when dealing with large input arrays, as shown in the Java and C++ examples of Approach 1. The choice between the two approaches depends on personal preference; Approach 1 is usually preferred for its conciseness.