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

Hints:
Assume the sequence is increasing, what if we find the largest consecutive difference?
Is the missing element in the middle of the segment with the largest consecutive difference?
For decreasing sequences, just reverse the array and do a similar process.

Finding the Missing Number In Arithmetic Progression in C++

As the first and the last element of the array is not the missed ones, thus we can compute the steps of the Arithmetic Progression. We can convert the numbers into the set, then we check the progressing numbers and return one that is not in the set. This requires O(N) space and O(N) time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int missingNumber(vector<int>& arr) {
        int d = (arr.back() - arr[0]) / (int)arr.size();
        if (d == 0) return arr[0];
        unordered_set s(begin(arr), end(arr));
        for (int i = 0; i < arr.size(); ++ i) {
            int t = (arr[0] + i * d);
            if (!s.count(t)) {
                return t;
            }
        }
        return arr[0];
    }
};

class Solution {
public:
    int missingNumber(vector<int>& arr) {
        int d = (arr.back() - arr[0]) / (int)arr.size();
        if (d == 0) return arr[0];
        unordered_set s(begin(arr), end(arr));
        for (int i = 0; i < arr.size(); ++ i) {
            int t = (arr[0] + i * d);
            if (!s.count(t)) {
                return t;
            }
        }
        return arr[0];
    }
};

The .size() returns unsigned integer, thus need converting to (int) to get the distance between two numbers in the Arithmetic Progression.

Actually, we don’t need to allocate the set, we can just compare with the numbers in the array. The following C++ code runs O(N) time and uses O(1) constant space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int missingNumber(vector<int>& arr) {
        int n = arr.size();
        int d = arr.back() - arr[0];
        int s = d / (int)arr.size();
        int t = arr[0];
        for (int i = 1; i < n; ++ i) {
            t += s;
            if (arr[i] != t) {
                return t;
            }
        }
        return arr[0];
    }
};

class Solution {
public:
    int missingNumber(vector<int>& arr) {
        int n = arr.size();
        int d = arr.back() - arr[0];
        int s = d / (int)arr.size();
        int t = arr[0];
        for (int i = 1; i < n; ++ i) {
            t += s;
            if (arr[i] != t) {
                return t;
            }
        }
        return arr[0];
    }
};

–EOF (The Ultimate Computing & Technology Blog) —