• Time:O(n)
• Space:O(1)

## C++

``````class Solution {
public:
int minPatches(vector<int>& nums, int n) {
int ans = 0;
int i = 0;      // point to nums
long miss = 1;  // min sum in [1, n] we might miss

while (miss <= n)
if (i < nums.size() && nums[i] <= miss) {
miss += nums[i++];
} else {
// greedily add miss itself to increase the range
// from [1, miss) to [1, 2 * miss)
miss += miss;
++ans;
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int minPatches(int[] nums, int n) {
int ans = 0;
int i = 0;     // point to nums
long miss = 1; // min sum in [1, n] we might miss

while (miss <= n)
if (i < nums.length && nums[i] <= miss) {
miss += nums[i++];
} else {
// greedily add miss itself to increase the range
// from [1, miss) to [1, 2 * miss)
miss += miss;
++ans;
}

return ans;
}
}
``````

## Python

``````class Solution:
def minPatches(self, nums: List[int], n: int) -> int:
ans = 0
i = 0     # point to nums
miss = 1  # min sum in [1, n] we might miss

while miss <= n:
if i < len(nums) and nums[i] <= miss:
miss += nums[i]
i += 1
else:
# greedily add miss itself to increase the range
# from [1, miss) to [1, 2 * miss)
miss += miss
ans += 1

return ans
``````