Hackbright Code Challenges

Coins

Coins

Whiteboard

Harder

Challenge

Medium

Concepts

Recursion

Download

coins.zip

Solution

Coins: Solution


You have an endless supply of dimes and pennies. How many different amounts of total change can you make using exactly num_coins number coins?

For example, when num_coins = 3, you can create 4 different kinds of change:

  • 3 cents from penny + penny + penny

  • 12 cents dime + penny + penny

  • 21 cents from dime + dime + penny

  • 30 cents from dime + dime + dime

So, you should have a function that returns the set {3, 12, 21, 30} when num_coins is 3.

For example:

>>> coins(1) == {1, 10}
True

>>> coins(2) == {2, 11, 20}
True

>>> coins(3) == {3, 12, 21, 30}
True

>>> coins(4) == {4, 13, 22, 31, 40}
True

>>> coins(10) == {10, 19, 28, 37, 46, 55, 64, 73, 82, 91, 100}
True

We given you a file, coins.py, with a placeholder function, coin:

coins.py
def coins(num_coins):
    """Find change from combinations of `num_coins` of dimes and pennies.

    This should return a set of the unique amounts of change possible.
    """

Implement the coins function. When this is successful, all tests should pass.

Hint

Recursion

You can solve this problem with recursion—each time you can add a coin, you can split into two paths, one where you add a penny and one where you add a dime. This kind of recursion, where you have two “tails”, is similar to the kind you’d use to look at every node in binary tree.

There’s also a simpler, non-recursive solution. Can you find both?