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/missing-number-in-arithmetic-progression/
// 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)

All Problems

All Solutions