2952. Minimum Number of Coins to be Added 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minimumAddedCoins(int[] coins, int target) {
        // 注意：硬币不能重复使用

        Arrays.sort(coins);

        int minAdd = 0;
        int i = 0;
        int start = 1; // range: [0, start - 1]
        while (start - 1 < target) {
            if (i < coins.length && coins[i] <= start) { // 当硬币小于等于 start 时，之前的 [0, start - 1] 区间与加上该硬币后的新区间 [coins[i], start - 1 + coins[i]] 可以合并
                start += coins[i];
                i++;
            } else {
                start += start; // 添加一个 start
                minAdd++;
            }
        }

        return minAdd;
    }
}

References

2952. Minimum Number of Coins to be Added