Project Euler 31: Investigating combinations of English currency denominations

Written by on 12 March 2011

Topics: Project Euler

Problem 31 of Project Euler honestly baffled me for a while. That lasted until I realised that there is a simple brute force solution. But enough blabbering, the problem reads

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:

1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p

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

As mentioned before I have found a brute force solution which is a completely viable way to go, and I have found a dynamic programming solution. For the problem size of 200p the solutions are equally fast, but for larger problems the dynamic programming solution is significantly faster.

Brute Force Solution

The brute force solution consist of a set of nested for loops, where the initial value of the inner loop is dependent on the outer. This way it is possible to test if there is a way of making a solution with 2p and up which is smaller than or equal to £2, we can always top the solution up with 1ps until we reach £2. The C# code looks as

int target  = 200;
int ways = 0;

for (int a = target; a >= 0; a -= 200) {
    for (int b = a; b >= 0; b -= 100) {
        for (int c = b; c >= 0; c -= 50) {
            for (int d = c; d >= 0; d -= 20) {
                for (int e = d; e >= 0; e -= 10) {
                    for (int f = e; f >= 0; f -= 5) {
                        for (int g = f; g >= 0; g -= 2) {
                            ways++;
                        }
                    }
                }
            }
        }
    }
}

I don’t think it is a pretty solution, but it works, and the result of running the code is

£2 can be generated in 73682 number of ways
Solution took 0 ms

Running the code in less than a millisecond is hard to complain about though.

Dynamic Programming

In order to make a solution using Dynamic Programming we need to be able to divide the problem into independent sub-problems. There are dimension which this can be done in for this problem, both the number of different coins but also the value we need to split. The problem is also covered here but I will try to give an alternative description of the solution.

The question we want to answer repeatedly is. “If I have to give change to n pennies, if I give back one coin of x how many ways can I give back the rest n-x pennies using only coins of value x or smaller.” Posing that question means that we can make a smaller problem, which we need to solve. And in the end we get a very small and easy problem to solve “if I want to give change to 1p using 1p, how many ways can this be done?”

Instead of breaking down the problem with the question posed above, we will instead build up an array of solutions so we can look up the answer to the question once we are ready to ask it. And let me show you by hand with a smaller example. Lets figure out how many ways we can give change to 5p using 1p and 2p. This should be doable by hand.

What we will do is build up an array of solutions, at first the array is build up for giving change to 1-5p using only 1p coins.

We need to initialise the array with the question. If we want to give change to 0p using a 1p coin, in how many different ways can we do that. And to that we define the answer to be 1. Now we are ready to answer “If I have to change to 1p using 1p coins, how many ways can I do that?”, so lets give back 1p and look up the value for n-x = 0p, which is 1 add this to the already found 0 solutions for a total of 1 solution.

012345
110000

Now we are ready to answer the question, if I want to give change to 2p using 1p coins, and give back 1p, in how many ways can I give back the remaining 1p?. So subtracting 1 from the solution, we can look up the last part of the question, since that was already answered. This goes on for all 5p until we have a solution array that looks like

012345
111111

If you think about it, it is rather obvious that there is only one way to give change to any amount using only 1p coins.

So now we are ready to treat the case when we have 2p coins as well. Since we can’t give back a 2p coin when we need to change 1p, there is no need to pose that question. Lets instead see how many ways we can give back 2p. If we use the 2p coin, we need to further give change to 0p. So that is a solution. Lets add that to the already found number of solutions, so the solution array looks like

012345
112111

For 3p we can also give a 2p coin and then we need to give change to 1p, which in the table and gives us one solution. So the total number of solutions for giving change on 3p, is 1+1.

012345
112211

Giving change on 4p. To answer that give 2p change and answer the question how many ways can we give change to n-x = 4-2 = 2p using 1p and 2p coins. The answer to that is in the table and is 2. So there are two ways to give back 2p, plus the already found number of solutions. So the result table now looks like

012345
112231

Lets just make a sanity check on that. 4p we can make change in 4x1p, 2p + 2x1p or 2x2p. Yep, that seems correct. We can do the same with the 5 giving change to 5p so the solution table looks like

012345
112233

You get the idea of how to build the solution now? Lets make the algorithm for it. It is completely analogue to what I just showed you by hand just with more coins and a larger value we need to give change to.

In C# it can be implemented as

int target = 200;
int[] coinSizes = { 1, 2, 5, 10, 20, 50, 100, 200 };
int[] ways = new int[target+1];
ways[0] = 1;

for (int i = 0; i < coinSizes.Length; i++) {
    for (int j = coinSizes[i]; j <= target; j++) {
        ways[j] += ways[j - coinSizes[i]];
    }
}

pretty compact piece of code.  Which keeps building up the answer until we reach the final goal.

Running the code results in

£2 can be generated in 73682 number of ways
Solution took 0 ms

So for such a small problem there is no difference in running time.

Closing Remarks

There is no apparent difference in running time between the two algorithms.  But the number of iterations we need to go through differs significantly.  The brute force algorithm needs to go through all 73682 solutions. The dynamic programming has to make 200 calculations for each coin type, which totals 1600 calculations, a difference which becomes even more significant for larger change values.

As usual you can find the source code for download. And once again I encourage you to correct my mistakes, ask questions, find other solutions and so on. I am uncertain if this approach to solving the problem is well enough explained, so let me know.

21 Comments For This Post I'd Love to Hear Yours!

  1. AlexFromBelgium says:

    Hey!
    I don’t understand how the brute force would even run…?

    int target = 200;
    int ways = 0;

    for (int a = target; a <= 0; a -= 200) {
    ...

    a is 200 -> is a smaller or equal to 0? No, ok, no loops…
    ways is 0 …

    What am I missing here :p please help me out! Great blog btw

  2. Kristian says:

    Hi Alex.

    The reason you don’t understand the brute force solution is most likely because I made a typo. The less than signs should have been greater than. They were in the source file and now they are in the post as well.

    Hope it makes more sense now, and thanks for spotting that error.

    /Kristian

  3. chubakueno says:

    I tried to solve this problem by I couldn’t with this code(gives 73685)

    #define to2(x) ((x)/2+1)
    int to5(x)
    {
        int acc=1;
        for(;x>0;x-=5)
            acc+=to2(x);
        return acc;
    }
    int to10(x)
    {
        int acc=1;
        for(;x>0;x-=10)
        acc+=to5(x);
        return acc;
    }
    int to20(x)
    {
        int acc=1;
        for(;x>0;x-=20)
            acc+=to10(x);
        return acc;
    }
    int to50(x)
    {
        int acc=1;
        for(;x>0;x-=50)
            acc+=to20(x);
        return acc;
    }
    int to100(x)
    {
        int acc=1;
        for(;x>0;x-=100)
            acc+=to50(x);
        return acc;
    }
    int main()
    {
    int test = to100(200)+1;
    printf(“%d”,test);
    return 0;
    }
    
  4. Kristian says:

    I don’t have any immidiate solution for the problem. However, you can try implementing the code I proposed in the code and compare the results with your results for much smaller amounts then 200. That could give you clues to where the bug is in the code.

    /Kristian

  5. b.b. says:

    As a matter of fact, any least coin cannot be split up any further. However, the driving momentum is a pretty different one: If we knew previous solutions for both an amount and its remainder, that is the amount decreased by a coin’s value, we knew everything there is to know to compute the amount’s current solution count. Of course, if an amount happens to be a coin’s value there is a trival solution. In other words, if we manage to handle solution counts for partial amounts and guarantee complete coin processing we are done. Thus there is neither a need to utilise the concept of a least coin, nor a convention to “give change to 0p”, which is a semantical desaster anyway, not to speak of: “to that we define the answer to be 1″. How to actually identify trivial solutions or to allow look-ups etc. are mere implementation details and not semantical matters at all. The algorithm’s most stunning feature, by the way, is its indifference towards any actual coinset including the coinset’s order – it does simpliciter not matter.

  6. Broken link for the dynamic programming pdf above.

    Thanks for the article!

  7. Bjarki Ágúst says:

    If anyone really wants to read that paper, I found it here. But Kristian does an excellent job of explaining it himself, so it shouldn’t matter.

  8. Mike says:

    Great solutions and analyses. Really like your blog. Keep up the good work. I, also have published several solutions. You can check them out at blog.dreamshire.com

  9. Kristian says:

    Hi Mike

    Thanks for the comment. Yes I am well familiar with your blog, I often read your solutions for some further insight into the problem after I have solved it.

  10. Anup says:

    here is a program to calculate the number of combinations.

    public class coin {

    public static void main(String arg[]) {
    System.out.println(“hi”);
    int num=0;
    for(int h=0; h<=1 ;h++)
    {
    int count=0;
    count=(h*200);
    if(count==200)
    {
    num+=1;
    break;
    }
    else{
    for(int i=0;i<=2;i++) {
    count=(h*200)+(i*100);
    if(count==200)
    {
    num+=1;
    break;
    }
    else{
    for(int j=0;j<=4;j++) {
    count=(h*200)+(i*100)+(j*50);
    if(count==200)
    {
    num+=1;
    break;
    }
    else{
    for(int k=0;k<=10;k++) {
    count=(h*200)+(i*100)+(j*50)+(k*20);
    if(count==200)
    {
    num+=1;
    break;
    }
    else{
    for(int l=0;l<=20;l++) {
    count=(h*200)+(i*100)+(j*50)+(k*20)+(l*10);
    if(count==200)
    {
    num+=1;
    break;
    }
    else{
    for(int m=0;m<=40;m++) {
    count=(h*200)+(i*100)+(j*50)+(k*20)+(l*10)+(m*5);
    if(count==200)
    {
    num+=1;
    break;
    }
    else{
    for(int n=0;n<=100;n++) {
    count=(h*200)+(i*100)+(j*50)+(k*20)+(l*10)+(m*5)+(n*2);
    if(count==200)
    {
    num+=1;
    break;
    }
    else{
    for(int o=0;o<=200;o++) {
    count=(h*200)+(i*100)+(j*50)+(k*20)+(l*10)+(m*5)+(n*2)+(o*1);
    if(count==200)
    {
    num++;
    }
    }
    }
    }
    }
    }
    }
    }
    }
    }
    }
    }
    }
    }
    }
    }
    System.out.println(num);
    }
    }

  11. cjw says:

    I believe the statement “The dynamic programming has to make 200 calculations for each coin type, which totals 1600 calculations”, is incorrect. For each coin type, i, the dynamic programming makes 201-coinSizes[i] calculations. For this problem, that totals to 1220 calculations.

  12. Is not this the same as finding the non-negative integer solutions to a linear equation ?

  13. Bjarki Ágúst says:

    It’s not hard to formulate the problem as such: Find the number of non-negative integer solutions to the following linear equation.

    On the other hand, I doubt that it helps when solving the problem.

  14. I understand what you are saying ! It is just a way of seeing the question differently and rather i should say the above program is actually a way of counting non-integer solutions of such equations

  15. Bjarki Ágúst says:

    Yeah, exactly! :)

  16. enrico giurin says:

    Here my solution based on an optimization of brute force

    int ways = 8; //ways with coin of the same type, 
    		//i.e.1x200 or 2x100 or 4x50
    		
    			for (n100 = 0; n100 <= 1; n100++) {
    				for (n50 = 0; n50 <= 3; n50++) {
    					if(sum(n100,n50,0,0,0,0, 0)>200) continue;
    					for (n20 = 0; n20 <= 9; n20++) {
    						if(sum(n100,n50,n20,0,0,0, 0)>200) continue;
    						
    						for (n10 = 0; n10 <= 19; n10++) {
    							if(sum(n100,n50,n20,n10,0,0, 0)>200) continue;
    							for (n5 = 0; n5 <= 39; n5++) {
    								if(sum(n100,n50,n20,n10,n5,0, 0)>200) continue;
    								for (n2 = 0; n2 <= 99; n2++) {
    									if(sum(n100,n50,n20,n10,n5,n2, 0)>200) continue;
    									for (n1 = 0; n1 <= 199; n1++) {
    										iterations++;
    
    										if (sum(n100,n50,n20,n10,n5,n2,n1) == 200) {
    											
    											System.out.println(n100 + "\t" + n50 + "\t"
    													+ n10 + "\t" + n5 + "\t"
    													+ n2 + "\t" + n1);
    											ways++;
    										}
    									}
    
    								}
    							}
    						}
    					}
    				}
    			}
    
  17. enrico giurin says:

    These are the results:

    Tot iterations: 14735000
    73682

  18. zakariae says:

    thanks for the solution. i did the brute force solution myself.for the recursive solution i find it harder to understand.i don’t know in many problems you explain clearly the analysis but for this i did’nt understand the array example.i wil reread and reread to get it understand

  19. Kristian says:

    This is certainly not the easiest problem to being wrapping your head around dynamic programming, and I am not sure if I have explained it well enough.

    If you have more specific questions, don’t hesitate asking them.

  20. Koray Tugay says:

    There is something I do not understand. Lets say available coins were only 2p.
    Brute Force solution then will be:

    for (int a = target; a >= 0; a -= 200) {
    ways++;
    }

    But here ways will be equal to 2…

    However it should be 1.

    Why?

  21. vishal says:

    i could’nt understand this part
    . If we want to give change to 0p using a 1p coin, in how many different ways can we do that. And to that we define the answer to be 1.
    this prob is very much related to coin change and subset sum..?

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.