Calculate Coin Count in Java

// This class illustrates techniques for calculating the number of different 
//  combinations of coins that can be used to reach a specific amount of money.
// In England the currency is made up of pounds, £ (dollars), and pence, p (pennies).
// There are commonly 8 types of coins in general circulation:
// 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

/**
 *  This is serious brute force. It's optimized a little bit because we are
 *   checking the limit for each coin counter.
 * 
 */ 
public class Problem031 {
    private static final boolean debug = false;

    public static int Solve(int pounds) {
        int result = 0;
        int i, j, total;               // 0   1   2   3    4    5    6     7
        int coins[] = new int[8];      // 1p, 2p, 5p, 10p, 20p, 50p, 100p, 200p
        int coinsMax[] = new int[8];   // 1p, 2p, 5p, 10p, 20p, 50p, 100p, 200p
        for (i = 0; i < 8; i++) {
            coins[i] = 0;
        }
        coinsMax[0] = 200;
        coinsMax[1] = 100;
        coinsMax[2] = 40;
        coinsMax[3] = 20;
        coinsMax[4] = 10;
        coinsMax[5] = 4;
        coinsMax[6] = 2;
        coinsMax[7] = 1;
        try {
            while (true) {
                total =   coins[0] * 1
                        + coins[1] * 2
                        + coins[2] * 5
                        + coins[3] * 10
                        + coins[4] * 20
                        + coins[5] * 50
                        + coins[6] * 100
                        + coins[7] * 200;
                if (total == (pounds * 100)) {
                    if (debug) {
                       for (int k = 0; k < coins.length; k++) { System.out.print(coins[k] + ", ");}
                       System.out.println(".");
                    }
                    result++;
                }
                for (i = 0; i < coins.length; i++) {
                    coins[i]++;
                    if (coins[i] > coinsMax[i]) {
                        if (i == coins.length - 1) {
                            throw new Exception("done");
                        }
                        coins[i] = 0;
                    } else {
                        break;
                    }
                }
            }
        } catch (Exception ex) {
            System.out.println("Solve(): + ex.");
        }
        return result;

    }
}

 

More by this Author


Comments 3 comments

Tradotto 7 years ago

Ha I love it. Throwing an exception to break out of a forever loop! I have never seen that before. Then again I spend a lot of time mucking around in C....


Tradotto 7 years ago

PS, what's the output of this program? How long did it take?


nicomp profile image

nicomp 7 years ago from Ohio, USA Author

The program will take anywhere from about 1 minute upwards, depending on the hardware. It's an interesting exercise in calculating. We don't expect 'little' programs to take so long.

    Sign in or sign up and post using a HubPages Network account.

    0 of 8192 characters used
    Post Comment

    No HTML is allowed in comments, but URLs will be hyperlinked. Comments are not for promoting your articles or other sites.


    Click to Rate This Article
    working