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.

0 | 1 | 2 | 3 | 4 | 5 |

1 | 1 | 0 | 0 | 0 | 0 |

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

0 | 1 | 2 | 3 | 4 | 5 |

1 | 1 | 1 | 1 | 1 | 1 |

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

0 | 1 | 2 | 3 | 4 | 5 |

1 | 1 | 2 | 1 | 1 | 1 |

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.

0 | 1 | 2 | 3 | 4 | 5 |

1 | 1 | 2 | 2 | 1 | 1 |

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

0 | 1 | 2 | 3 | 4 | 5 |

1 | 1 | 2 | 2 | 3 | 1 |

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

0 | 1 | 2 | 3 | 4 | 5 |

1 | 1 | 2 | 2 | 3 | 3 |

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.

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

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

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

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

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.

Broken link for the dynamic programming pdf above.

Thanks for the article!

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.

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

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.

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);

}

}

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.

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

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.

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

Yeah, exactly! 🙂

Here my solution based on an optimization of brute force

These are the results:

Tot iterations: 14735000

73682

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

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.

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?

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

There’s a solution to this written in Lisp in SICP (Structure and Interpretation of Computer Programs http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html). Here’s my tweaked version

(define (count-change amount)

(cc amount 8))

(define (cc amount kinds-of-coins)

(cond ((= amount 0) 1)

((or (< amount 0) (= kinds-of-coins 0)) 0)

(else (+ (cc amount

(- kinds-of-coins 1))

(cc (- amount

(first-denomination kinds-of-coins))

kinds-of-coins)))))

(define (first-denomination kinds-of-coins)

(cond ((= kinds-of-coins 1) 1)

((= kinds-of-coins 2) 2)

((= kinds-of-coins 3) 5)

((= kinds-of-coins 4) 10)

((= kinds-of-coins 5) 20)

((= kinds-of-coins 6) 50)

((= kinds-of-coins 7) 100)

((= kinds-of-coins 8) 200)))

(count-change 200)

Does your brute force not count fort he solution where it is 200 1p?

I’m having a difficult time seeing how the scenario where 2p or 2 1p is used. The same issue with 5p or 5 1p, and so on.

I used a recursive algorithm, but I am not sure how it would compare to the other solutions.

Sorry I’m not sure what happened but coins1 is supposed to be coins

coins “c” in square brackets

Your brute force solution is incorrect. In the body of last loop you should increment ways only when the loop variable becomes 0.

Great solution and explanation!

I originally wrote up a solution using a recursive algorithm.

While it was fairly easy to do, I knew that there must be a better optimized solution.

(Much like the grid problem counting the ways to get from top left to bottom right, using dynamic programming).

I started formulating a solution, but got stuck. Your explanation cleared it up for me well, and I wrote my own solution in Python in a few minutes.