330. Patching Array

T: O(n)
S: O(1)

class Solution {
    public int minPatches(int[] nums, int n) {
        int result = 0;
        long miss = 1; // n maybe very big
        int i = 0;
        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss) { // miss cover numbers
                miss += nums[i];
                i++;
            } else { // nums[i] > miss, so we have to find another patch to match miss
                miss += miss;
                result++; // so actually add patches happend at double miss
                // then it can cover more range by doubling miss
                // if we can cover (1,6) -> then add a 7 we can cover to 7 (1,7) ->
                // also we can cover (1+7, 6+7) -> (7, 14)
                // means we can cover (1,7) and (7, 14) -> so it's (1, 14)
            }
        }
        return result;
    }
}

/***
cal the sum...
and we'll find the first miss by number sum
nums = [1,2,3,8] and n = 16

sum:
1
3
6. -> cover (1 to 6)


1,14. + 8

1, 22 -> bigger than all numbers

1, 44
1, 88


T: O(n)
S: O(1)
 */