// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (234 votes, average: 4.91 out of 5)
Loading...

Project Euler Solutions

Project Euler 31 Solution

Project Euler 31 Solution

Project Euler 31: Investigating combinations of English currency denominations


Project Euler 31 Problem Description

Project Euler 31: 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.
download arrowUse this link to get the Project Euler 31 Solution Python 2.7 source.

Afterthoughts

  • See also, Project Euler 76 Solution:
  • 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

Discussion

6 Responses to “Project Euler 31 Solution”

  1. Hi, exactly what does this line mean?
    ways[i] += ways[i-coin]

    Thanks,
    Judy

    Posted by Judy | April 20, 2017, 2:59 PM
  2. This code is indeed brilliant, but I have no idea how it works!

    Posted by Richard | January 18, 2017, 5:08 AM
  3. This is very elegant code. Thanks for posting. Much prettier than my brute force list of combinations. 🙂

    Posted by Tom R | June 18, 2013, 12:53 PM
  4. 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!

    Posted by Lee A. Newberg | May 18, 2009, 1:31 PM
  5. This solution is brilliant! My code was over 60 lines long. Thanks for the post.

    Posted by Harvard Bound | April 26, 2009, 11:37 PM

Post a comment