Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array.

Return the minimum number of patches required.

&nbsp;
Example 1:

Input: nums = [1,3], n = 6
Output: 1
Explanation:
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:

Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].


Example 3:

Input: nums = [1,2,2], n = 5
Output: 0


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 1000
	1 &lt;= nums[i] &lt;= 104
	nums is sorted in ascending order.
	1 &lt;= n &lt;= 231 - 1


class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
	#pre-process for convenience
        nums.append(n+1)
        t=1
        sum=1
        rs=0
        if nums[0]!=1:
            nums=[1]+nums
            rs+=1
# the idea is sum from index 0 to index i should cover 1 to that sum*2 then we go form left to right to cover upto n
        while sum<n:
            if sum<nums[t]-1:
                sum+=(sum+1)
                rs+=1
            else:
                sum+=nums[t]
                t+=1
        return rs
class Solution {
     public int minPatches(int[] nums, int n) {
        long sum = 0;
        int count = 0;
        for (int x : nums) {
            if (sum >= n) break;
            while (sum+1 < x && sum < n) { 
                ++count;
                sum += sum+1;
            }
            sum += x;
        }
        while (sum < n) {
            sum += sum+1;
            ++count;
        }
        return count;
    }
}
class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        nums.push_back(0);
        sort(nums.begin(), nums.end());
        long sum = 0;
        int ans = 0;
        for(int i = 1; i < nums.size(); i++){
            while((long)nums[i] > (long)(sum + 1)){
                ans++;
                sum += (long)(sum + 1);
                if(sum >= (long)n)
                    return ans;
            }
            sum += nums[i];
            if(sum >= (long)n)
                return ans;
        }
        while(sum < (long)n){
            ans++;
            sum += (long)(sum + 1);
        }
        return ans;
    }
};
// time complexity:
// while loop is - o(n) beacuse we can potentially get to n with nums array full of ones and we will pass on each of them
// in some cases it will hit o(logn) if the nums array is pretty empty
var minPatches = function(nums, n) {
    // nums is sorted so we don't have to sort it
    let index = 0;
    let sumCanCreate = 0;
    let patchCount = 0;
    while(sumCanCreate < n) {
        // if we can't create nums[index] or we at the end of nums and can't create n.
        // we can create nums[index] only if it is lower or equal to sumCanCreate+1.
        if(sumCanCreate+1 < nums[index] || (index >= nums.length && sumCanCreate+1 < n)) {
            patchCount++;
            // because we "patch" the next number in the sequence.
            sumCanCreate += (sumCanCreate+1);
        // if we can create nums[index].
        } else {
            // we can create anything from current sumCanCreate to (sumCanCreate + nums[index]).
            sumCanCreate += nums[index];
            index++;
        }
    }
    return patchCount;
};
Patching Array