// 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.

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.
|73682|

Afterthoughts

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