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{(a_1 + a_n)n}{2}$, where $n$ is the number of terms in the arithmetic series, the first term is $a_1$, 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_1$, and the last term is $a_n$. Therefore, the sum of the array is $\frac{(a_1 + a_n)(n + 1)}{2}$.
Thus, the missing number is $\frac{(a_1 + a_n)(n + 1)}{2} - \sum_{i = 0}^n a_i$.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.
1 2 3 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 |
|
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_1$, and the last term is $a_n$. The common difference $d$ is $\frac{a_n - a_1}{n}$.
Traverse the array, and if $a_i \neq 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)$.
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 |
|