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.

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
  1. 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
  1. 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.

Python Solution

1from typing import List
2
3class Solution:
4    def missing_number(self, nums: List[int]) -> int:
5        # Calculate the expected sum of the arithmetic series using the formula
6        # S = n/2 * (first_element + last_element)
7        # Here, 'n' is the number of elements the array is supposed to have,
8        # which is one more than the current number of elements due to the missing number
9        n = len(nums) + 1
10        expected_sum = n * (nums[0] + nums[-1]) // 2
11
12        # Subtract the actual sum from the expected sum to find the missing number
13        actual_sum = sum(nums)
14        missing_number = expected_sum - actual_sum
15
16        return missing_number
17      
18# Example usage:
19# sol = Solution()
20# print(sol.missing_number([3, 0, 1]))  # It should return the missing number in the sequence
21

Java Solution

1import java.util.Arrays;
2
3class Solution {
4    // Method to find the missing number in the sequence
5    public int missingNumber(int[] nums) {
6        // Calculate the expected length of the series including the missing number
7        int length = nums.length;
8      
9        // Compute the expected sum of the series using the arithmetic series formula:
10        // Sum = (first number + last number) * number of terms / 2
11        // Since the array is missing one number, we consider the length as (length + 1)
12        // Here we assume the series starts at 0 and ends with length, hence we add only arr[0]
13        int expectedSum = (0 + length) * (length + 1) / 2;
14      
15        // Compute the actual sum of the array's elements
16        int actualSum = Arrays.stream(nums).sum();
17
18        // The missing number is the difference between the expected and actual sums
19        return expectedSum - actualSum;
20    }
21}
22

C++ Solution

1#include <vector>       // Include necessary header for vector usage
2#include <numeric>      // Include header for std::accumulate function
3
4class Solution {
5public:
6    // Function to find the missing number in an arithmetic progression
7    int missingNumber(std::vector<int>& nums) {
8        int size = nums.size(); // Store the size of the array
9      
10        // Calculate the sum of the first and last elements in the array
11        // and multiply by the count of numbers in the complete sequence (size + 1)
12        // then divide by 2 to get the expected sum of the sequence if it were complete
13        int expectedSum = (nums[0] + nums[size - 1]) * (size + 1) / 2;
14      
15        // Compute the actual sum of the elements in the given array
16        int actualSum = std::accumulate(nums.begin(), nums.end(), 0);
17      
18        // The difference between expected and actual sum is the missing number
19        return expectedSum - actualSum;
20    }
21};
22

Typescript Solution

1// Import the 'reduce' method for array summation
2import { reduce } from 'lodash';
3
4// Function to find the missing number in an arithmetic progression
5function missingNumber(nums: number[]): number {
6    let size: number = nums.length; // Store the length of the array
7
8    // Calculate the sum of the first and last elements in the array
9    // and multiply by the count of numbers in the complete sequence (size + 1)
10    // then divide by 2 to get the expected sum of the sequence if it were complete
11    let expectedSum: number = (nums[0] + nums[size - 1]) * (size + 1) / 2;
12  
13    // Compute the actual sum of the elements in the given array
14    let actualSum: number = reduce(nums, (sum, value) => sum + value, 0);
15
16    // The difference between the expected and actual sum is the missing number
17    return expectedSum - actualSum;
18}
19

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.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫