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.
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. Imagine 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 .
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:
[1, miss) = [1, 1) = emptynums[i] is less than or equal to miss[1, miss + nums[i])i by 1miss, extends the range to [1, miss + miss)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:
Lemma
If the greedy algorithm needs to patch numbers to cover , it is impossible to patch less than numbers to do the same.
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:
otherwise will not be covered and so on so forth.
Finally, 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.
Complexity Analysis
Time complexity : . In each iteration, we either increase the index i or we double the variable miss. The total number of increment for index i is and the total number of doubling miss is
Space complexity : . We only need three variables, patches, i and miss.