## 330. Patching Array

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.

**Example 1:**

Input:nums=`[1,3]`

,n=`6`

Output:1Explanation:Combinations ofnumsare`[1], [3], [1,3]`

, which form possible sums of:`1, 3, 4`

. Now if we add/patch`2`

tonums, 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.

**Example 2:**

Input:nums=`[1,5,10]`

,n=`20`

Output:2Explanation:The two patches can be`[2, 4]`

.

**Example 3:**

Input:nums=`[1,2,2]`

,n=`5`

Output:0

## Rust Solution

```
struct Solution;
impl Solution {
fn min_patches(nums: Vec<i32>, n: i32) -> i32 {
let mut res = 0;
let mut miss: i64 = 1;
let mut i = 0;
while miss <= n as i64 {
if i < nums.len() && nums[i] as i64 <= miss {
miss += nums[i] as i64;
i += 1;
} else {
miss += miss;
res += 1;
}
}
res
}
}
#[test]
fn test() {
let nums = vec![1, 3];
let n = 6;
let res = 1;
assert_eq!(Solution::min_patches(nums, n), res);
let nums = vec![1, 5, 10];
let n = 20;
let res = 2;
assert_eq!(Solution::min_patches(nums, n), res);
let nums = vec![1, 2, 2];
let n = 5;
let res = 0;
assert_eq!(Solution::min_patches(nums, n), res);
}
```

Having problems with this solution? Click here to submit an issue on github.