## Number of ways of representing n cents using quarters, dimes, nickels and pennies

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.

My initial thoughts:

• Base case: $n < 0$. No way to do it.
• Recursion: Represent $n$ by using 1 quarter if possible + # ways of representing $(n-25)$ cents. Or, Represent $n$ by using 1 nickel if possible + # ways of representing $(n-10)$ cents. Or, Represent $n$ by using 1 nickels if possible + # ways of representing $(n-5)$ cents. And we always have 1 way to represent $n$ cents using $n$ pennies.

My initial codes:

public static int waysOfRepresentingNCents(int n) {
if (n < 0)
return 0;
else {
int ways = 0;
if (n >= 25)
ways += waysOfRepresentingNCents(n - 25);
if (n >= 10)
ways += waysOfRepresentingNCents(n - 10);
if (n >= 5)
ways += waysOfRepresentingNCents(n - 5);
ways += 1;
return ways;
}
}

Logic error.

• INPUT: n = 15.
• EXPECTED OUTPUT: 6 ways of representing 15 cents
• ACTUAL OUTPUT: 7.
• PROBLEM: Duplicate counting: 10 + 5 and 5 + 10 are the same way of representing 15 cents but they are counted twice. So we should have ordering.

Solution:

public static int makeChange(int n, int denom) {
int next_denom = 0;
switch (denom) {
case 25:
next_denom = 10;
break;
case 10:
next_denom = 5;
break;
case 5:
next_denom = 1;
break;
case 1:
return 1;
}
int ways = 0;
for (int i = 0; i * denom <= n; i++) {
ways += makeChange(n - i * denom, next_denom);
}
return ways;
}