(same as 330) 2952. Minimum Number of Coins to be Added

T: O(nlogn)

S: O(1)

class Solution {
    public int minimumAddedCoins(int[] coins, int target) {
        long miss = 1;
        int i = 0;
        int result = 0;
        
        Arrays.sort(coins);

        while (miss <= target) {
            if (i < coins.length && coins[i] <= miss) {
                miss += coins[i];
                i++;
            } else {
                miss += miss;
                result++;
            }
        }
        return result;
    }
}

/**

1 2 4 -> (1,2,3,4)
5

miss = 1+1 = 2
nums[i]<= 2

miss+= miss

 */