Tutorial :Understanding Project Euler #31


Could anyone explain me problem 31 of project euler? I don't understand the problem clearly.

Is the problem saying to calculate the coins in any order like:

2*£1 or perhaps 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p ?


I had problems understanding this problem as well, not being used to British currency.

There are 100 pence in a pound. The following coins (in pence) are available: 1, 2, 5, 10, 20, 50, 100 and 200.

You are asked in how many different ways you can combine these values to create 200 pence.

As an example, there are 4 ways to form 5 pence:

  • 1, 1, 1, 1, 1
  • 1, 1, 1, 2
  • 1, 2, 2
  • 5

Good luck!


The question is basically how many possible combinations are there to get 2£ worth of money (= 200p) when you have the 8 different types of coins available.

Here are just a few (trivial) possible combinations:

  • 1 x 2£
  • 2 x 1£
  • 200 x 1p
  • 1 x 1£ + 100 x 1p
  • ...

The question is: how many such combinations are possible?


You could use recursion to consider all the amount which are less that £2. (and then add the difference as pence)


You have to break this problem down into the question of how many ways you can make each coin value with coins of the same or lower values. This would lead you to something like this (I hope my assumptions are correct):

  • 1p

    A_1p = {{1p}}  |A_1p| = 1  
  • 2p

    A_2p = {{2p}, {1p,1p}}  |A_2p| = 1 + 1 = 2  
  • 5p

    A_5p = {{5p}, {2p,2p,1p}, {2p,1p,1p,1p}, {1p,1p,1p,1p,1p}}  |A_5p| = 1 + 3 = 4  
  • 10p

    A_10p = {{10p},           {5p,5p}, {5p,2p,2p,1p}, {5p,2p,1p,1p,1p}, {5p,1p,1p,1p,1p,1p},           {2p,2p,1p,2p,2p,1p}, {2p,2p,1p,2p,1p,1p,1p,}, {2p,2p,1p,1p,1p,1p,1p,1p,},           {2p,1p,1p,1p,2p,1p,1p,1p,}, {2p,1p,1p,1p,1p,1p,1p,1p,1p},           {1p,1p,1p,1p,1p,1p,1p,1p,1p,1p},           {2p,2p,2p,2p,2p,2p}          }  |A_10p| = 1 + 10 + 1 = 12  
  • …


This problem is a special case of a very well known problem called Subset Sum (http://en.wikipedia.org/wiki/Subset_Sum)


I thought the problem statement was clear. It lists the coins as:

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

As such, it is clear about the value of a pound in terms of pence. I think the question is more about the eventual goal of the problem. It asks

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

The confusion here seems to be about order. Having solved this problem, I will state that order is unimportant in the solution. All that matters is the number of coins of each denomination required to make up the total of 200p.

I'll add the suggestion that this is a small problem, very solvable with simple recursion. If you are unsure about how to proceed, a place to look is in the theory of the partitions of a number.


This is a tricky solution that i didn't understand at all. A solution is at http://blog.csdn.net/No_End_Point/archive/2009/06/26/4301149.aspx

And here a good piece of theory: Integer Partition in Wikipedia.

From here: http://tardate.blogspot.com/2008/10/rolling-project-euler-on-ruby.html


Hey, simple dp, using python:

ways = [0]*201  ways[0] = 1  for x in [1,2,5,10,20,50,100,200]:      for i in xrange(x, 201):          ways[i] += ways[i-x]  print ways[200]  


Less efficient than DP, but runs in 1/2 a second for this particular problem. Simple recursion:

solve    []     s         = 0    solve    (c:ct) 0         = 1    solve    (c:ct) s | c > s = solve ct s    solve cs@(c:ct) s         = (solve cs (s - c)) + (solve ct s)    answer = solve [200,100,50,20,10,5,2,1] 200  

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Next Post »