# Calculate the number of ways of representing n cents

**Problem Statement**

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

**Solution**

This is a recursive problem, so let’s figure out how to do makeChange(n) using prior solutions (i e , sub-problems) Let’s say n = 100, so we want to compute the number of ways of making change of 100 cents What’s the relationship to its sub-problems?

We know that makeChange(100):

= makeChange(100 using 0 quarters) + makeChange(100 using 1 quarter) + makeChange(100 using 2 quarter) + makeChange(100 using 3 quarter) + makeChange(100 using 4 quarter)

Can we reduce this further? Yes!

= makeChange(100 using 0 quarters) + makeChange(75 using 0 quarter) + makeChange(50 using 0 quarters) + makeChange(25 using 0 quarters) + 1

Now what? We’ve used up all our quarters, so now we can start applying our next biggest denomination: dimes. This leads to a recursive algorithm that looks like this:

**Code**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
public class NCents { static int solve(int n, int denom) { int nextDenom = 0; switch (denom) { case 25: nextDenom = 10; break; case 10: nextDenom = 5; break; case 5: nextDenom = 1; break; case 1: return 1; } int ans = 0; for (int i = 0; i * denom <= n; i++) { ans += solve(n - i * denom, nextDenom); } return ans; } public static void main(String[] args) { int n = 100; System.out.println(solve(n, 25)); } } |