> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/google/330-patching-array.md).

# 330 Patching Array

## 330. [Patching Array](https://leetcode.com/problems/patching-array/description/)

## 1. Question

Given a sorted positive integer arraynumsand an integern, 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:**\
nums=`[1, 3]`,n=`6`\
Return`1`.

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:**\
nums=`[1, 5, 10]`,n=`20`\
Return`2`.\
The two patches can be`[2, 4]`.

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

## 2. Implementation

思路:

(1) 这题很有意思，要求我们找到数组里需要加多少个数，使得数组可以表示\[1,n]。假设我们当前在nums\[i]这个位置上可以表示范围为\[1,n]的数，n为nums\[0]到nums\[i]所有数的和，当我们在数组加入n + 1时，我们就可以表示\[1, 2n + 1]的数了，其中\[n + 1, 2n + 1]这个范围的数可以通过新加的n + 1表示。

(2) 所以我们的做法是用一个变量miss表示\[0,n]之间最小的不能表示的值，我们将它初始化为1，如果将它初始化为0的话，没有意义。那么此时我们能表示的范围是\[0, miss)，表示此时我们能表示0到miss-1的数，如果此时的num <= miss，那么我们可以把我们能表示数的范围扩大到\[0, miss+num)，如果num > miss，那么此时我们需要添加一个数，为了能最大限度的增加表示数范围，利用贪心的思想，我们加上miss它本身

**(1) Greedy**

```java
class Solution {
    public int minPatches(int[] nums, int n) {
        long miss = 1;
        int count = 0;
        int index = 0;

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

## 3. Time & Space Complexity

**Greedy**: 时间复杂度O(n), 空间复杂度O(1)