330. Patching Array

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.

• Record : 27min 6sec
• Space : O(1)
• Time : O(N)

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long tot = 0, res = 0;
        for(int i = 0; i < nums.size() && tot < n && nums[i] <= n; i++) {
            while(tot + 1 < nums[i]) {
                tot = tot + tot + 1;
                res++;
            }
            tot += nums[i];
        }
        while(tot < n) {
            tot = tot + tot + 1;
            res++;
        }
        return res;
    }
};