LeetCode 1228. Missing Number In Arithmetic Progression Solution in Java, C++, Python & More | Explanation + Code

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 ^{(a₁ + a_n)n}⁄₂, where n is the number of terms in the arithmetic series, the first term is a₁, and the last term is a_n.

Since the array given in the problem is an arithmetic series with one missing number, the number of terms in the array is n + 1, the first term is a₁, and the last term is a_n. Therefore, the sum of the array is ^{(a₁ + a_n)(n + 1)}⁄₂.

Thus, the missing number is ^{(a₁ + a_n)(n + 1)}⁄₂ - ∑_{i = 0}ⁿ a_i.

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

PythonJavaC++GoTypeScript

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

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; } }(code-box)

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; } };(code-box)

func missingNumber(arr []int) int { n := len(arr) x := (arr[0] + arr[n-1]) * (n + 1) / 2 y := 0 for _, v := range arr { y += v } return x - y }(code-box)

function missingNumber(arr: number[]): number { const x = ((arr[0] + arr.at(-1)!) * (arr.length + 1)) >> 1; const y = arr.reduce((acc, cur) => acc + cur, 0); return x - y; }(code-box)

Solution 2: Find Common Difference + Traverse

Since the array given in the problem is an arithmetic series with one missing number, the first term is a₁, and the last term is a_n. The common difference d is ^{a_n - a₁}⁄_n.

Traverse the array, and if a_i ≠ a_{i - 1} + d, then return a_{i - 1} + d.

If the traversal completes without finding the missing number, it means all numbers in the array are equal. In this case, directly return the first number of the array.

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

PythonJavaC++GoTypeScript

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](code-box)

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]; } }(code-box)

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]; } };(code-box)

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] }(code-box)

function missingNumber(arr: number[]): number { const d = ((arr.at(-1)! - arr[0]) / arr.length) | 0; for (let i = 1; i < arr.length; ++i) { if (arr[i] - arr[i - 1] !== d) { return arr[i - 1] + d; } } return arr[0]; }(code-box)