# Euler Problem 31

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 + 1 50p + 2 20p + 1 5p + 1 2p + 3 1p

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