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 + 150p + 220p + 15p + 12p + 31p

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

Sometimes brute force is the simplist. This one ran in 22 seconds.

public class Euler31

{

public static void main(String[] args)

{

System.out.print(“Problem 31:\n”);

Euler31 e = new Euler31();

System.out.print(“Answer = ” + e.Problem()+ “\n”);

}

public String Problem ()

{

int c = 0;

for (int P2 = 0; P2 <= 200; P2=P2+200)

for (int P1 = 0; P1 <= 200; P1=P1+100)

for (int p50 = 0; p50 <= 200; p50=p50+50)

for (int p20 = 0; p20 <= 200; p20=p20+20)

for (int p10 = 0; p10 <= 200; p10=p10+10)

for (int p5 = 0; p5 <= 200; p5=p5+5)

for (int p2 = 0; p2 <= 200; p2=p2+2)

for(int p1 = 0; p1 <= 200; p1++)

if (P2+P1+p50+p20+p10+p5+p2+p1 == 200)

c++;

return String.valueOf(c);

}

}