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]
.Let's look at the example 1, let curr be the current number in the arrray, cover be the maximum number the numbers being covered from 1.
When curr = 1, cover = 1;
When curr = 3, since there is gap between cover and curr, we need to fill it in, so insert 2, and update cover to 1 + 2 + 3 = 6;
Done.
Example 2.
curr = 1, cover = 1;
curr = 5, fill in the gap between 1 and 5, insert 2, cover = 1+2 = 3, gap is still there between 3 and 5, insert cover+1=4, update cover = 1+2+3=6, no gap any more, update cover = 1+2+3+5=11
curr = 10, no gap, and update cover = 11+10=21
21>20, Done.
So the two most important findings are
1) when we insert a number, the coverage will be increased by that number,
2) next insert number will be the coverage+1.
So our algorithm is following:
let cover=0, insert=0
1. go through the numbers (curr) in the list until cover >= n
while curr > cover+1 and cover<n,
insert cover+1
update cover = cover + cover+1
increase insert by 1
2. while cover < n
insert cover+1
update cover = cover + cover+1
increase insert by 1
No comments:
Post a Comment