Welcome to Subscribe On Youtube
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 <= 10000 <= 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.
-
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; } } -
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; } }; -
class Solution: def missingNumber(self, arr: List[int]) -> int: return (arr[0] + arr[-1]) * (len(arr) + 1) // 2 - sum(arr) -
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] }