Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1228.html
1228. Missing Number In Arithmetic Progression
Level
Easy
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
.
Then, a value from arr
was removed that was not the first or last value in the array.
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] <= 10^5
Solution
For the original arithmetic progression (no value removed), all pairs of adjacent numbers in the array have the same difference.
After a value is removed, then one pair of adjacent numbers in the array will have a difference that has a greater absolute value.
If a difference with a greater absolute value is found, then find the two numbers with such the difference with a greater absolute value, and the removed value is the average value of the two numbers.

class Solution { public int missingNumber(int[] arr) { int length = arr.length; int prevDif = arr[1]  arr[0]; for (int i = 2; i < length; i++) { int curDif = arr[i]  arr[i  1]; if (Math.abs(curDif) < Math.abs(prevDif)) return arr[i  1]  curDif; else if (Math.abs(curDif) > Math.abs(prevDif)) return arr[i  1] + prevDif; prevDif = curDif; } return arr[length  1] + prevDif; } }

// OJ: https://leetcode.com/problems/missingnumberinarithmeticprogression/ // Time: O(N) // Space: O(1) class Solution { public: int missingNumber(vector<int>& A) { int N = A.size(), d = (A.back()  A[0]) / N; if (d == 0) return A[0]; for (int i = 1; i < N; ++i) { if (A[i] != A[i  1] + d) return A[i  1] + d; } return 1; } };

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