# Exercise #37: Change Maker

makeChange(30)   {'quarters': 1, 'nickels': 1} American currency has coins in the denominations of 1 (pennies), 5 (nickels), 10 (dimes), and 25 cents (quarters). Imagine that we were programming a cash register to dispense correct change. In this exercise, we would need to calculate the number of each coin for a given amount of change.

Exercise Description

Write a `makeChange()` function with an amount parameter. The `amount` parameter contains an integer of the number of cents to make change for. For example, `30` would represent 30 cents and 125 would represent \$1.25. This function should return a dictionary with keys `'quarters'`, 'dimes', `'nickels'`, and 'pennies', where the value for a key is an integer of the number of this type of coin.

The value for a coin’s key should never be `0`. Instead, the key should not be present in the dictionary. For example, makeChange(5) should return {'nickels': 1} and not {'quarters’: 0, 'dimes': 0, 'nickels': 1, 'pennies': 0}.

For example, `makeChange(30)` would returns the dictionary `{'quarters': 1, 'nickels': 5}` to represent the coins used for 30 cents change. The function should use the minimal number of coins. For example, `makeChange(10)` should return `{'dimes': 1}` and not {'nickels': 2}, even though they both add up to 10 cents.

These Python `assert` statements stop the program if their condition is `False`. Copy them to the bottom of your solution program. Your solution is correct if the following `assert` statements’ conditions are all True:

assert makeChange(30) == {'quarters': 1, 'nickels': 1}

assert makeChange(10) == {'dimes': 1}

assert makeChange(57) == {'quarters': 2, 'nickels': 1, 'pennies': 2}

assert makeChange(100) == {'quarters': 4}

assert makeChange(125) == {'quarters': 5}

Try to write a solution based on the information in this description. If you still have trouble solving this exercise, read the Solution Design and Special Cases and Gotchas sections for additional hints.

Prerequisite concepts: modulo operator, integer division

Solution Design

First, our `makeChange()` function should create an empty dictionary in a variable named `change` to store the results to return. Next, we need to determine the amount of each type of coin, starting with the largest denominations (25-cent quarters) to the smallest (1-cent pennies). This way, we don’t accidentally use more than the minimum amount of coins by determining we need, for example, two 5-cent nickels instead of one 10 cent dime.

Let’s start with quarters. Before doing any calculation, if the amount of change to make is less than 25, then we can skip this calculation entirely since there are zero quarters. Otherwise, if the amount of change to make is divisible by 25, say the `amount` parameter is `125`, then we can determine the number of quarters by dividing `amount` by `25`: 125 / 25 evaluates to `5.0`.

However, if it isn’t divisible by 25, our result will have a fractional part: `135 / 25` evaluates to 5.4. We can only add whole numbers of quarters to our change, not 0.4 quarters. Using the `//` integer division operator, we can ensure that we only put whole numbers of coins into our change dictionary: both `125 // 25` and 135 // 25 evaluate to `5`.

To deduct the amount of change held by the quarters, we can set change to the amount remaining after removing 25 cent increments. The word “remaining” hints that we should use the `%` modulo operator. For example, if we need to make 135 cents of change and use 5 quarters for 125 of those cents, we would need to use other coins for the 135 % 25 or `10` remaining cents.

This handles calculating the number of quarters used to make change. We would then copy-paste this code and make modifications for dimes, nickels, and pennies (in that order). When we finish processing the number of pennies, the `amount` parameter will be 0 and the `change` dictionary will contain the correct amounts of each coin.

Special Cases and Gotchas

Because this exercise specifies that the change should be made from the minimal number of coins, there is only one correct answer for any given amount of change. The most important thing to get right in this algorithm is to calculate the coins in order from largest to smallest, otherwise you’ll end up in a situation where, say, you use two nickels instead of one dime.

Also, be sure to use the `//` integer division operator instead of the `/` division operator to calculate the number of coins. Python’s regular division operator evaluates to floating-point numbers, which may contain a fractional part. (Even if it doesn’t, Python still evaluates the result to a float: 125 / 25 evaluates to the float `5.0` and not the integer `5`.) Integer division always evaluates to integers and doesn’t have this potential problem.

Because pennies represent 1 cent, you can set the number of pennies in change to whatever the `amount` parameter is at the end of the function as long as it is greater than zero.

Now try to write a solution based on the information in the previous sections. If you still have trouble solving this exercise, read the Solution Template section for additional hints.

Solution Template

Try to first write a solution from scratch. But if you have difficulty, you can use the following partial program as a starting place. Copy the following code from https://invpy.com/makechange-template.py and paste it into your code editor. Replace the underscores with code to make a working program:

def makeChange(amount):

# Create a dictionary to keep track of how many of each coin:

change = ____

if amount >= ____:

change['quarters'] = amount // ____

# Reduce the amount by the value of the quarters added:

amount = amount % ____

if amount >= ____:

change['dimes'] = ____ // ____

# Reduce the amount by the value of the dimes added:

amount = ____ % ____

if amount >= ____:

change['nickels'] = ____ // ____

# Reduce the amount by the value of the nickels added:

amount = ____ % ____