You are given a list of integers nums that used to be an arithmetic sequence. Given that a number was removed, and that the number was not the first or the last element, return the removed number.
Constraints
2 ≤ n ≤ 100,000
Example 1
Input
nums = [1, 3, 5, 9]
Output
7
Explanation
If we add 7 in to this sequence, we get [1, 3, 5, 7] which is an arithmetic sequence.
Find the Missing Number in the Arithmetic Progression Sequence
We can find the maximum gap between two consecutive numbers. We need to check if the arithmetic sequence is ascending or non-ascending order. Then, the half of the gap will be the correct distance between two consecutive numbers.
Then, we just need to iterate the sequence to see if next one is missing:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | int solve(vector<int>& nums) { int m1 = INT_MAX; int m2 = -INT_MAX + 1; for (int i = 1; i < nums.size(); ++ i) { m1 = min(m1, nums[i] - nums[i - 1]); m2 = max(m2, nums[i] - nums[i - 1]); } int d; if (nums[1] > nums[0]) { d = m2 / 2; } else { d = m1 / 2; } for (int i = 0; i + 1 < nums.size(); ++ i) { if (nums[i] + d != nums[i + 1]) { return nums[i] + d; } } return nums[0]; } |
int solve(vector<int>& nums) {
int m1 = INT_MAX;
int m2 = -INT_MAX + 1;
for (int i = 1; i < nums.size(); ++ i) {
m1 = min(m1, nums[i] - nums[i - 1]);
m2 = max(m2, nums[i] - nums[i - 1]);
}
int d;
if (nums[1] > nums[0]) {
d = m2 / 2;
} else {
d = m1 / 2;
}
for (int i = 0; i + 1 < nums.size(); ++ i) {
if (nums[i] + d != nums[i + 1]) {
return nums[i] + d;
}
}
return nums[0];
}Time complexity is O(N) where N is the number of the nodes in the sequence and space complexity is O(1) constant.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution: def solve(self, nums): m1 = float("inf") m2 = float("-inf") for i in range(1, len(nums)): x = nums[i] - nums[i - 1] m2 = max(m2, x) m1 = min(m1, x) if nums[1] >= nums[0]: d = m2 // 2 else: d = m1 // 2 for i in range(len(nums) - 1): if nums[i] + d != nums[i + 1]: return nums[i] + d return nums[0] |
class Solution:
def solve(self, nums):
m1 = float("inf")
m2 = float("-inf")
for i in range(1, len(nums)):
x = nums[i] - nums[i - 1]
m2 = max(m2, x)
m1 = min(m1, x)
if nums[1] >= nums[0]:
d = m2 // 2
else:
d = m1 // 2
for i in range(len(nums) - 1):
if nums[i] + d != nums[i + 1]:
return nums[i] + d
return nums[0]Another approach is to first compute the sum of the current sequence. Then, since the first and last element won’t be missing, we can compute the expected sum including the missing number using the arithmetic progression sum forumula. Then the difference is the missing number.
1 2 3 4 5 6 | int solve(vector<int>& nums) { int s = std::accumulate(begin(nums), end(nums), 0); int first = nums[0]; int last = nums.back(); return (first + last) * (nums.size() + 1) / 2 - s; } |
int solve(vector<int>& nums) {
int s = std::accumulate(begin(nums), end(nums), 0);
int first = nums[0];
int last = nums.back();
return (first + last) * (nums.size() + 1) / 2 - s;
}The complexity is O(N) but it should be faster than the first approach since it requires only 1 pass. The space complexity is O(1) constant.
1 2 3 4 | class Solution: def solve(self, nums): s = sum(nums) return (nums[0] + nums[-1]) * (len(nums) + 1) // 2 - s |
class Solution:
def solve(self, nums):
s = sum(nums)
return (nums[0] + nums[-1]) * (len(nums) + 1) // 2 - s–EOF (The Ultimate Computing & Technology Blog)
loading...
Last Post: Algorithm to Remove Duplicates in Linked List using Hash Set
Next Post: Teaching Kids Programming - Prefix Sum Algorithm to Compute the Interval Sums
