1228. Missing Number In Arithmetic Progression

Problem Description

The problem provides an array arr where the values were originally in an arithmetic progression. An arithmetic progression is a sequence of numbers in which the difference between consecutive terms is constant. This constant difference is missing in the current array because one of the values, which was neither the first nor the last, has been removed.

Our task is to find out which value was removed from the array, knowing that the remaining values continue to have a constant difference between them, except for the place where the value was removed.

Intuition

The intuition behind the solution comes from the properties of an arithmetic progression. In a complete arithmetic progression with n terms, the average of the first term a1 and the last term an is also the average of all terms in the sequence. Thus, the sum of the entire progression can be calculated using the formula:

1sum = average * number_of_terms
2sum = ((a1 + an) / 2) * n

If a term in the middle is missing, the sum of the terms that are present will be less than the expected sum of the full arithmetic progression by exactly the value of the missing term. We can rearrange the formula to find the missing term as follows:

1missing_term = expected_sum - actual_sum

The solution approach uses this fact to find the missing number. It calculates the expected sum by using the formula with len(arr) + 1 terms (since one term is missing) and then subtracts the actual sum of the array arr. What we are left with is the value of the missing term. The code is a direct implementation of this logic.

Learn more about Math patterns.

Solution Approach

The solution uses a direct mathematical approach and does not rely on complex data structures, algorithms, or patterns. It is a straightforward translation of the mathematical insight into Python code.

Here are the steps the code takes to implement the solution:

1. Calculate the expected sum of the arithmetic progression if it were complete. This is done using the formula ((arr[0] + arr[-1]) * (len(arr) + 1)) // 2. The arr[0] represents the first element, and arr[-1] represents the last element in the list. Since one item is missing, the original length before removal would have been len(arr) + 1.

2. Calculate the actual sum of the available elements in the array using the built-in sum(arr) function.

3. The difference between the expected sum of a complete arithmetic progression and the actual sum of the given array represents the value of the missing element. So, missing_number = expected_sum - actual_sum.

The Python code for the solution method missingNumber implements these steps, and this is why the entire logic of finding the missing number is condensed into a single line:

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

By executing this line of code, we calculate and return the missing element directly. The use of integer division // ensures that the result is an integer, which matches the problem's requirement that elements of the array are integers.

Example Walkthrough

Let's go through a small example to illustrate the solution approach:

Suppose we have an array arr representing an arithmetic progression with one value removed:

1arr = [5, 7, 11, 13]

To find the missing number, we would:

1. Calculate the expected sum of the arithmetic progression if it were complete.

In this example, the first element a1 is 5, and the last element an is 13. The length of the original array before a number was removed would be len(arr) + 1 = 5. Using the formula, the expected sum is:

1expected_sum = ((a1 + an) / 2) * n = ((5 + 13) / 2) * 5 = (18 / 2) * 5 = 9 * 5 = 45

2. Calculate the actual sum of the available elements in the array.

Now we use the sum function to find the actual sum:

1actual_sum = sum(arr) = 5 + 7 + 11 + 13 = 36

3. Calculate the difference between the expected sum and the actual sum to find the missing term.

Next, we find the missing term:

1missing_number = expected_sum - actual_sum = 45 - 36 = 9

The missing term in the arithmetic progression is 9. We can check this by adding the missing term to the array:

1arr = [5, 7, 9, 11, 13]

Now arr is a complete arithmetic progression with a common difference of 2 between each term.

Python Code Implementation

Applying the example into the Python code, we would have:

1def missingNumber(arr):
2    return (arr[0] + arr[-1]) * (len(arr) + 1) // 2 - sum(arr)
3
4# Given array
5arr = [5, 7, 11, 13]
6
7# Call the function to find the missing number
8print(missingNumber(arr))  # Output: 9

By running this code with our example array [5, 7, 11, 13], we find that the output is 9, which confirms that the missing number has been correctly identified using the solution approach.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n), where n is the length of the input array arr. This is because the primary operation that depends on the size of the input is the sum(arr) function, which iterates through each element of the array once to compute the sum.

Other operations, like computing arr[0] + arr[-1] and len(arr) + 1, are executed in constant time, O(1), meaning that their execution time does not depend on the size of the input array.

Space Complexity

The space complexity of the code is O(1).

This is because the code uses a fixed amount of space regardless of the input size. The space used for storing the result of arr[0] + arr[-1] and the intermediate calculations for (len(arr) + 1) // 2 - sum(arr) does not scale with the size of the input array; it remains constant.

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