Leet Code Daily 2024-06-16 - Patching Array
Solution
Assuming we have completed range [1, x] and the next given but not used number is y,
- If
y <= x + 1, then we just use and expand the range to[1, x + y]. - Otherwise, we must patch a new number
x + 1, and the new range would be[1, x + x + 1].
Code
class Solution {
public:
int minPatches(vector<int>& nums, int n) {
int i = 0, ans = 0;
for (long long r = 0; r < n;) {
if (i < nums.size() && nums[i] <= r + 1) {
r += nums[i++];
} else {
r += r + 1;
ans++;
}
}
return ans;
}
};