# [LeetCode] 330. Patching Array 数组补丁

2021年09月15日 阅读数：1

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range `[1, n]` inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.html

Example 1:
nums = `[1, 3]`n = `6`
Return `1`.java

Combinations of nums are `[1], [3], [1,3]`, which form possible sums of: `1, 3, 4`.
Now if we add/patch `2` to nums, the combinations are: `[1], [2], [3], [1,3], [2,3], [1,2,3]`.
Possible sums are `1, 2, 3, 4, 5, 6`, which now covers the range `[1, 6]`.
So we only need `1` patch.python

Example 2:
nums = `[1, 5, 10]`n = `20`
Return `2`.
The two patches can be `[2, 4]`.post

Example 3:
nums = `[1, 2, 2]`n = `5`
Return `0`.ui

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.this

Java:url

```public int minPatches(int[] nums, int n) {
long miss = 1;
int count = 0;
int i = 0;

while(miss <= n){
if(i<nums.length && nums[i] <= miss){
miss = miss + nums[i];
i++;
}else{
miss += miss;
count++;
}
}

return count;
}　```

Python:code

```class Solution(object):
def minPatches(self, nums, n):
"""
:type nums: List[int]
:type n: int
:rtype: int
"""
patch, miss, i = 0, 1, 0
while miss <= n:
if i < len(nums) and nums[i] <= miss:
miss += nums[i]
i += 1
else:
miss += miss
patch += 1

return patch　　```

C++:orm

```class Solution {
public:
int minPatches(vector<int>& nums, int n) {
long miss = 1, res = 0, i = 0;
while (miss <= n) {
if (i < nums.size() && nums[i] <= miss) {
miss += nums[i++];
} else {
miss += miss;
++res;
}
}
return res;
}
};
```

C++:htm

```class Solution {
public:
int minPatches(vector<int>& nums, int n) {
long miss = 1, k = nums.size(), i = 0;
while (miss <= n) {
if (i >= nums.size() || nums[i] > miss) {
nums.insert(nums.begin() + i, miss);
}
miss += nums[i++];
}
return nums.size() - k;
}
};
```