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