#31 - Coin sums

in Project Euler on 5%

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p)

It is possible to make £2 in the following way:

1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p

How many different ways can £2 be made using any number of coins?

To solve this, we note that in a certain set of coin values, we can either use a certain coin or not use it.

For example, with £2 given above, we can use £2 coin or not.

  • If we use it, then there is only one way to make the value.
  • If we don’t use it, our next option is to use the £1 coin. At this point, the problem turns into “How many ways can we create £2 - £1 = £1 using the coins?”

In this way, we can recurse down. The base case will be when we have exactly £0 left. A few special cases include when we have a negative amount, or when we have no more coins left to choose.

# file: "problem031.py"
def makeChange(value, coins):
    # Coins will be in decreasing order i.e. largest is first
    # Can't make change
    if value < 0:
        return 0
    # I can make no change by choosing nothing
    elif value == 0:
        return 1
    # I can't make something out of nothing
    elif value > 0 and len(coins) == 0:
        return 0
    # Recursive call: Have a case where I choose the largest
    # coin while decrementing value and a case where I skip it
    # and don't decrement value
    else:
        return makeChange(value - coins[0], coins) + makeChange(value, coins[1:len(coins)])

After this, we simply make the array of coin values, and call our function.

# file: "problem031.py"
coins = [200, 100, 50, 20, 10, 5, 2, 1]
print(makeChange(200, coins))

The result of running is

73682
1.9159925933914943 seconds.

Thus, there are 73682 ways to make £2 from the coins given.