1228

1228. Missing Number In Arithmetic Progression (Easy)

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.

Companies:
VMware, Facebook

Related Topics:
Array, Math

Solution 1.

// OJ: https://leetcode.com/problems/missing-number-in-arithmetic-progression/
// Author: github.com/lzl124631x
// 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;
    }
};

Solution 2. Binary Search (L <= R)

// OJ: https://leetcode.com/problems/missing-number-in-arithmetic-progression/
// Author: github.com/lzl124631x
// Time: O(logN)
// Space: O(1)
class Solution {
public:
    int missingNumber(vector<int>& A) {
        int N = A.size(), d = (A.back() - A[0]) / N, L = 0, R = N - 1;
        if (d == 0) return A[0];
        while (L <= R) {
            int M = (L + R) / 2;
            if (A[M] == A[0] + d * M) L = M + 1;
            else R = M - 1;
        }
        return A[0] + d * L;
    }
};

Solution 3. Binary Search (L < R)

// OJ: https://leetcode.com/problems/missing-number-in-arithmetic-progression/
// Author: github.com/lzl124631x
// Time: O(logN)
// Space: O(1)
class Solution {
public:
    int missingNumber(vector<int>& A) {
        int N = A.size(), d = (A.back() - A[0]) / N, L = 0, R = N - 1;
        if (d == 0) return A[0];
        while (L < R) {
            int M = (L + R) / 2;
            if (A[M] == A[0] + d * M) L = M + 1;
            else R = M;
        }
        return A[0] + d * L;
    }
};