Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Calculate the number of ways of representing n cents

Sharing is caring!

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