PreviousNext
Coding/Searching and sorting

Canonical coin change

Write codeEasy10 min

Your task

You are given an amount and a list of coin denominations that always includes 1 and is canonical, meaning repeatedly taking the largest coin that still fits always yields an optimal answer (as with [1, 5, 10, 25]). Return the minimum number of coins needed to make exactly the amount. Example: amount 63 with coins [1, 5, 10, 25] needs 6 coins (25 + 25 + 10 + 1 + 1 + 1). An amount of 0 needs 0 coins.

Examples

min_coins(amount: int, coins: list[int]) -> int
Example 1
Inputmin_coins(63, [1, 5, 10, 25])
Output6