This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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:**

*nums* = `[1, 3]`

, *n* = `6`

Return `1`

.

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.

**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`

.

**Credits:**

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

b'

\n## Solution

\n

\n

'
**Intuition**

For any missing number, if we want to cover it, we have to add at least one number smaller or equal to that number. Otherwise, it will not be covered.\nImagine you want to give someone change of cents, and you don\'t have enough coins. You will need to ask for coin less than or equal to .

\n**Algorithm**

Suppose `miss`

is the smallest missing number, then we know that `[1, miss)`

(left-closed, right-open) is already covered . In order to cover `miss`

, we have to add something smaller than or equal to `miss`

. Otherwise, there is no way we can cover it.

For example, you have any array `nums = [1,2,3,8]`

and `n = 16`

. The numbers already covered is in the ranges `[1, 6]`

and `[8, 14]`

. In other words, `7, 15, 16`

are missing. If you add patches larger than `7`

, then `7`

is still missing.

Suppose the number we added is then, the ranges `[1, miss)`

and `[x, x + miss)`

are both covered. And since we know that `x <= miss`

, the two ranges will cover the range `[1, x + miss)`

. We want to choose as large as possible so that the range can cover as large as possible. Therefore, the best option is `x = miss`

.

After we covered `miss`

, we can recalculate the coverage and see what\'s the new smallest missing number. We then patch that number. We do this repeatedly until no missing number.

Here is the recipe of this greedy algorithm:

\n- \n
- Initialize the range
`[1, miss)`

=`[1, 1)`

= empty \n - While n is not covered yet \n
- if the current element
`nums[i]`

is less than or equal to`miss`

- \n
- extends the range to
`[1, miss + nums[i])`

\n - increase
`i`

by 1 \n

\n - extends the range to
- otherwise
- \n
- patch the array with
`miss`

, extends the range to`[1, miss + miss)`

\n - increase the number of patches \n

\n - patch the array with
- Return the number of patches \n

**Example:**

`nums = [1,2,3,8]`

and `n = 80`

iteration | `miss` | covered range | `i` | `nums[i]` | patches | comment |
---|---|---|---|---|---|---|

0 | 1 | [1, 1) | 0 | 1 | 0 | |

1 | 2 | [1, 2) | 1 | 2 | 0 | |

2 | 4 | [1, 4) | 2 | 3 | 0 | |

3 | 7 | [1, 7) | 3 | 8 | 0 | |

4 | 14 | [1, 14) | 3 | 8 | 1 | patch 7 |

5 | 22 | [1, 22) | 4 | none | 1 | |

6 | 44 | [1, 44) | 4 | none | 2 | patch 22 |

7 | 88 | [1, 88) | 4 | none | 3 | patch 44 |

**Correctness**

One may ask how do you know this is correct? In this section, we will prove that the greedy algorithm always gives the smallest possible number of patches:

\n*Lemma*

\n\nIf the greedy algorithm needs to patch numbers to cover , it is impossible to patch less than numbers to do the same.

\n

*Proof by contradiction*

For a given number and array , suppose the patches found by greedy algorithm is . If there is another set of patches , with , then we have , otherwise is not covered. And since adding cannot cover which means the sum of all the elements including is smaller than . Thus adding will also not cover . And so we have:

\n\n\n

\notherwise will not be covered and so on so forth.

\n\n\n

\nFinally, we can see that since is not enough to cover , therefore is also not enough to cover . This contradicts the fact that covers . **This completes the proof.**

Thus, the greedy algorithm will always return the fewest patches possible. Even through for particular cases, there could be many different ways to patch. But none of them will have fewer patches than the greedy algorithm does.

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : . In each iteration, we either increase the index

\n`i`

or we double the variable`miss`

. The total number of increment for index`i`

is and the total number of doubling`miss`

is \n \n - \n
Space complexity : . We only need three variables,

\n`patches`

,`i`

and`miss`

. \n