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.
[1, 3], n =
Combinations of nums are
, , [1,3], which form possible sums of:
1, 3, 4.
Now if we add/patch
2 to nums, the combinations are:
, , , [1,3], [2,3], [1,2,3].
Possible sums are
1, 2, 3, 4, 5, 6, which now covers the range
So we only need
[1, 5, 10], n =
The two patches can be
[1, 2, 2], n =
Special thanks to @dietpepsi for adding this problem and creating all test cases.
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
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 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
[1, 1)= empty
nums[i]is less than or equal to
[1, miss + nums[i])
miss, extends the range to
[1, miss + miss)
nums = [1,2,3,8] and
n = 80
|4\n||14\n||[1, 14)\n||3\n||8\n||1\n||patch 7\n|
|6\n||44\n||[1, 44)\n||4\n||none\n||2\n||patch 22\n|
|7\n||88\n||[1, 88)\n||4\n||none\n||3\n||patch 44\n|
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
If 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\n
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
otherwise will not be covered and so on so forth.\n
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.\n
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
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 \n
Space complexity : . We only need three variables,