How Many Ways Can You Make 36 Cents?

There are 24 ways to make 36 cents using U.S. currency. This type of problem is known as the "coin change" problem, which is a form of the classic problem of integer partition where only certain numbers are considered valid to add up to the whole.

In order to solve this problem, a recursive algorithm should be used. Start with the largest coins you can to solve the problem, then work your way down to the smallest coins. If you use a quarter and a dime, there's one penny left, which yields one way. If you use a quarter with no dimes, that leaves you with being able to use either zero, one or two nickels, which yields three more ways. Without any quarters, you'd have to use three dimes and either zero or one nickels, which yields two more ways. With only two dimes, you could use between zero and three nickels, which yields four ways. With only one dime, you could use between zero and five nickels, which yields six ways. Finally, to solve the problem, if you only can use nickels and pennies, you can use between zero and seven nickels which yields eight ways. The sum of all of these steps is twenty-four pennies, which is the answer.

Similar Articles