Prev - #36 Reverse String | Table of Contents | Next - #38 Random Shuffle
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 the amount is enough to add quarters, add them:
if amount >= ____:
change['quarters'] = amount // ____
# Reduce the amount by the value of the quarters added:
amount = amount % ____
# If the amount is enough to add dimes, add them:
if amount >= ____:
change['dimes'] = ____ // ____
# Reduce the amount by the value of the dimes added:
amount = ____ % ____
# If the amount is enough to add nickels, add them:
if amount >= ____:
change['nickels'] = ____ // ____
# Reduce the amount by the value of the nickels added:
amount = ____ % ____
# If the amount is enough to add pennies, add them:
if amount >= 1:
change[____] = amount
return change
The complete solution for this exercise is given in Appendix A and https://invpy.com/makechange.py. You can view each step of this program as it runs under a debugger at https://invpy.com/makechange-debug/.
Prev - #36 Reverse String | Table of Contents | Next - #38 Random Shuffle