## Project Euler 31: Investigating combinations of English currency denominations

#### Project Euler 31 Problem Description

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?

#### Analysis

This is a typical problem that demonstrates the use of partitions which can be solved by using dynamic programming. To keep this problem simple: order does not matter, there are always enough coins to make a combination and we’re not looking for the optimal way to make change. This a perfect application for tested algorithms where this problem has been used as an example. As the details and nuances of dynamic programming are somewhat involved; we have provided some links below for a better explanation:

Coin Change – Algorithmist

Dynamic Programming Solution to the Coin Changing Problem

#### Project Euler 31 Solution

Runs < 0.001 seconds in Python 2.7.Use this link to get the Project Euler 31 Solution Python 2.7 source.

#### Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose*define*to reveal the answer.

#### Afterthoughts

- See also, Project Euler 76 Solution: How many different ways can one hundred be written as a sum of at least two positive integers?
- This problem only wants the number of combinations. It would be a different approach if they wanted a set of combinations.

*Project Euler 31 Solution last updated*

Hi, exactly what does this line mean?

ways[i] += ways[i-coin]

Thanks,

Judy

Meaning, why does it work for this problem?

This code is indeed brilliant, but I have no idea how it works!

This is very elegant code. Thanks for posting. Much prettier than my brute force list of combinations. 🙂

For 2x pounds the number of ways to make change with coins of 1, 2, 5, 10, 20, 50, 100, and 200 pence is:

Ways(2x) = (63 – 16524x + 121100x^2 + 862127x^3 + 1656620x^4 +1395380x^5 + 543200x^6 + 80000x^7) / 63.

I can compute that pretty quickly even for 10^12 pounds!

This solution is brilliant! My code was over 60 lines long. Thanks for the post.