## Thursday, June 29, 2017

### Count Coins

There are four types of common coins in US currency:
quarters (25 cents)
dimes (10 cents)
nickels (5 cents)
pennies (1 cent)

There are 6 ways to make change for 15 cents:
A dime and a nickel;
A dime and 5 pennies;
3 nickels;
2 nickels and 5 pennies;
A nickel and 10 pennies;
15 pennies.

How many ways are there to make change for a dollar
using these common coins? (1 dollar = 100 cents).

[Source http://rosettacode.org]

import java.util.ArrayList;
import java.util.List;

public class CountCoins {
private static final int QUARTER = 25;
private static final int DIME = 10;
private static final int NICKEL = 5;

public static List solution(int cents) {
List options = new ArrayList<>();
for (int quarters = 0; quarters <= cents / QUARTER; quarters++) {
int afterQuarters = cents - quarters * QUARTER;
for (int dimes = 0; dimes <= afterQuarters / DIME; dimes++) {
int afterDimes = afterQuarters - dimes * DIME;
for (int nickels = 0; nickels <= afterDimes / NICKEL; nickels++) {
int pennies = afterDimes - nickels * NICKEL;
options.add(String.format("Quarters=%d, Dimes=%d, Nickels=%d, Pennies=%d", quarters, dimes, nickels, pennies));
}
}
}
return options;
}

public static void main(String[] args) {
List options = solution(100);
options.forEach(System.out::println);
}
}