Home > Programming > Project euler 31: Coin sums

Project euler 31: Coin sums


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) and £2 (200p).

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

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

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

This a very nice Dynamic programming question:

def noOfCoins(coins, n):
    noOfWays= [x * 0 for x in range(n + 1)]
    noOfWays[0] = 1
    for i in range(len(coins)):
        for j in range(coins[i], n + 1):
            noOfWays[j] = noOfWays[j] + noOfWays[j - coins[i]]
    return noOfWays[n]
if __name__ == '__main__':
    coins = [1,2,5,10,20,50,100,200]
    n = 200
    print(noOfCoins(coins, n))

Answer: 73682
Time Complexity: O(number of available coins * n) ~ o(N)
Space Complexity: O(N)

Categories: Programming Tags: ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: