1228. Missing Number In Arithmetic Progression

Description

In some array arr, the values were in arithmetic progression: the values arr[i + 1] - arr[i] are all equal for every 0 <= i < arr.length - 1.

A value from arr was removed that was not the first or last value in the array.

Given arr, return the removed value.

 

Example 1:

Input: arr = [5,7,11,13]
Output: 9
Explanation: The previous array was [5,7,9,11,13].

Example 2:

Input: arr = [15,13,12]
Output: 14
Explanation: The previous array was [15,14,13,12].

 

Constraints:

  • 3 <= arr.length <= 1000
  • 0 <= arr[i] <= 105
  • The given array is guaranteed to be a valid array.

Solutions

Solution 1: Arithmetic Series Sum Formula

The sum formula for an arithmetic series is $\frac{n(a_1 + a_n)}{2}$, where $n$ is the number of terms in the arithmetic series, $a_1$ is the first term of the arithmetic series, and $a_n$ is the last term of the arithmetic series.

Since the array given in the problem is an arithmetic series and is missing a number, the number of terms in the array is $n + 1$, the first term is $a_1$, and the last term is $a_n$, so the sum of the array is $\frac{n + 1}{2}(a_1 + a_n)$.

Therefore, the missing number is $\frac{n + 1}{2}(a_1 + a_n) - \sum_{i = 0}^n a_i$.

The time complexity is $O(n)$, and the space complexity is $O(1)$. Where $n$ is the length of the array.

Python Code
1
2
3

class Solution:
    def missingNumber(self, arr: List[int]) -> int:
        return (arr[0] + arr[-1]) * (len(arr) + 1) // 2 - sum(arr)

Java Code
1
2
3
4
5
6
7
8

class Solution {
    public int missingNumber(int[] arr) {
        int n = arr.length;
        int x = (arr[0] + arr[n - 1]) * (n + 1) / 2;
        int y = Arrays.stream(arr).sum();
        return x - y;
    }
}

C++ Code
1
2
3
4
5
6
7
8
9

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

Go Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func missingNumber(arr []int) int {
	n := len(arr)
	d := (arr[n-1] - arr[0]) / n
	for i := 1; i < n; i++ {
		if arr[i] != arr[i-1]+d {
			return arr[i-1] + d
		}
	}
	return arr[0]
}

Solution 2

Python Code
1
2
3
4
5
6
7
8

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 Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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++ Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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];
    }
};