330. Patching Array - cocoder39/coco39_LC GitHub Wiki

330. Patching Array

[1, range) is can be formed by the sum of visited elements. Supposing current range is 10, which means the visited elements can form [1, 10).

• if nums[i] <= range, the sum [1, 10) can be extended to [1, 10) + nums[i] + [nums[i]+1, 10+nums[i]) = [1, nums[i] + 10). range would increase at least by 1, thus time complexity is O(n)
• if nums[i] > range, If next element is 13, which is greater than 10. The new element can extend the sum to [1, 10)+ 13 + [14, 23) = [1, 10) + [13, 23). There is a gap [10, 13). In order to remove the gap, we need to patch 10 into array. range would binary increase, therefore time complexity is O(log n).

time complexity is O(n)

int minPatches(vector<int>& nums, int n) {
        int res = 0;
        long range = 1;
        
        int i = 0;
        while (range <= n) {
            if (i < nums.size() && nums[i] <= range)
                range += nums[i++];
            else {
                range += range;
                res++;
            }
        }
        return res;
    }