How to Find the Missing Number In Arithmetic Progression?

  • 时间:2020-09-18 17:01:02
  • 分类:网络文摘
  • 阅读:83 次

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) —

推荐阅读:
用天平称来解决的数学问题  偶然中的必然  求比值和化简化有什么区别?  公历年份四年一闰,为什么整百数的年份又不全闰?  怎样判断一个较大的数是不是质数?  圆形跑道的直径有多少米?  为什么1既不是质数,也不是合数?  数学中1有哪些意义?  为什么至少有两列涂色方式相同?  一道求零件个数问题 
评论列表
添加评论