rolling-counter.java

// http://blog.sandwormz.com/2010/11/rolling-counter-algorithm-pattern.html
class Scratch {
    public static void main(String[] args) {
        convertPennies(150);
    }

    public static String[] labels = {"Nickles", "Dimes", "Quarters", "Dollars"};
    public static int[] units = {5, 10, 25, 100};

    public static void convertPennies(int pennies) {
        int[] arr = new int[units.length];

        int j;  // last incremented bit
        do {
            if (getValue(arr) == pennies) {
                printCurrency(pennies, arr);
            }
            // increment (always starting from first bit)
            arr[0]++;
            // carry
            for (j = 0; j < arr.length && getValue(arr) > pennies; j++) {
                // don't carry last bit
                if (j < arr.length - 1) {
                    arr[j] = 0;
                    arr[j + 1]++;
                }
            }
        } while (j < arr.length);
    }

    public static int getValue(int[] currency) {
        int mTotalValue = 0;
        for (int i = 0; i < currency.length; i++) {
            mTotalValue += currency[i] * units[i];
        }
        return mTotalValue;
    }

    private static void printCurrency(int pennies, int[] currency) {
        for (int i = 0; i < currency.length; i++) {
            System.out.print(String.valueOf(currency[i]));
            System.out.print(" " + labels[i] + " ");
        }
        System.out.println(" and " +
                           (pennies - getValue(currency)) + " pennies");
    }
}