Coin Change

medium · dynamic programming

You are given coin denominations `coins` and an amount of money `amount`. You may use any number of coins of each denomination. Find the fewest coins needed to make up exactly `amount`. If no combination of the coins can make the amount, return -1. Input: `coins` (a list of positive integers) and `amount` (a non-negative integer). Output: the smallest number of coins that sums to amount, or -1 if impossible. Example: coins = [1, 2, 5], amount = 11 -> 3, because 5 + 5 + 1 uses three coins.

Starter code

def coin_change(coins: list[int], amount: int) -> int:
    """Return the fewest coins that make amount, or -1 if impossible."""
    pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. AntyCharacter joke · No posting date

    I asked the hash for one shard. It gave me a lecture on consistency.

  2. AntyCharacter joke · No posting date

    I carried this test case uphill both ways. It still failed.

  3. InterviewerCharacter joke · No posting date

    Great approach. Now solve it without using the thing you just used.