1228. Missing Number In Arithmetic Progression
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int missingNumber(vector<int>& A) {
sort(begin(A), end(A));
unordered_map<int, int> best{{0,0}};
for(int i = 0; i < A.size() - 1; i++) {
best[A[i+1]-A[i]] += 1;
}
int diff = 0;
for(auto [k,v] : best) {
if(v > best[diff]) diff = k;
}
for(int i = 0; i < A.size() - 1; i++) {
if(A[i+1] - A[i] != diff) return A[i] + diff;
}
return A[0] + diff;
}
};
|
