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: . No way to do it.
- Recursion: Represent by using 1 quarter if possible + # ways of representing cents. Or, Represent by using 1 nickel if possible + # ways of representing cents. Or, Represent by using 1 nickels if possible + # ways of representing cents. And we always have 1 way to represent cents using 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;
}
}

**Comments after running:**

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

### Like this:

Like Loading...

*Related*

sophie

Oct 20, 2013@ 19:29:00Hey Runhe, do u know the time complexity of the solution? Thanks !

Anonymous

Jul 16, 2014@ 20:28:33You did not explain how you got to second solution after finding out error that duplicate counting is made in first solution