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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s