330. Patching Array

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.

Solution:

Greedy, use every possible value to increase the range.
Use the right patch to maximize the range.
Eg. If current range is [1,20], and we should add 21 to the array to maximize the range, which will make the range increase to [1,41]. We can't add any number that is larger than 21, which will make 21 not in the range. If we add any number smaller than 21, the range is not maximized.
if current range is [1,20] the next value in nums is 30, and the target is 69. We should add 21 as a patch to make range increase to [1,41], then we can use 30 to increase the range, [1,71] which will cover 69.
Time complexity: O(nums.length,+lg(n))) either we add patch each time to cover n (each time the range will double or we use the numbers in the array )

 public int minPatches(int[] nums, int n) {  
     int count=0;  
     long covered=0;  
     int i=0;  
     while(covered<n){  
       if(i>=nums.length || covered+1<nums[i]){  
         count++;  
         covered=2*covered+1;  
       }  
       else covered+=nums[i++];  
     }  
     return count;  
   }  
 }