Minimum Number of Coins to be Added — LeetCode 2952 Python Solution

The problem

You are given a 0-indexed integer array coins, representing the values of the coins available, and an integer target. An integer x is obtainable if there exists a subsequence of coins that sums to x.

Example

Input

coins = [1,4,10], target = 19

Output

2

Explanation

We need to add coins 2 and 8. The resulting array will be [1,2,4,8,10].

Python solution

class Solution:
    def minimumAddedCoins(self, coins: List[int], target: int) -> int:
        coins.sort()
        s = 1
        ans = i = 0
        while s <= target:
            if i < len(coins) and coins[i] <= s:
                s += coins[i]
                i += 1
            else:
                s <<= 1
                ans += 1
        return ans

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2952. Minimum Number of Coins to be Added is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems