Python function: Find Change from purchase amount

Question

I'm looking for the most efficient way to figure out a change amount (Quarters, dimes, nickels, and pennies) from a purchase amount. The purchase amount must be less than $1, and the change is from one dollar. I need to know how many quarters, dimes, nickels, and pennies someone would get back.

Would it be best to set up a dictionary?

Answer 1

Your best bet is to probably have a sorted dictionary of coin sizes, and then loop through them checking if your change is greater than the value, add that coin and subtract the value, otherwise move along to the next row in the dictionary.

Eg

Coins = [50, 25, 10, 5, 2, 1]
ChangeDue = 87
CoinsReturned = []
For I in coins:
   While I >= ChangeDue:
        CoinsReturned.add(I)
        ChangeDue = ChangeDue - I

Forgive my lousy python syntax there. Hope that's enough to go on.

Answer 2

Gee, you mean this isn't problem 2b in every programming course any more? Eh, probably not, they don't seem to teach people how to make change any more either. (Or maybe they do: is this a homework assignment?)

If you find someone over about 50 and have them make change for you, it works like this. Say you have a check for $3.52 and you hand the cashier a twnty. They'll make change by saying "three fifty-two" then

• count back three pennies, saying "three, four, five" (3.55)
• count back 2 nickels, (3.60, 3.65)
• count back a dime (3.75)
• a quarter (4 dollars)
• a dollar bill (five dollars)
• a $5 bill (ten dollars)
• a $10 bill (twenty.)

That's at heart a recursive process: you count back the current denomination until the current amount plus the next denomination comes out even. Then move up to the next denomination.

You can, of course, do it iteratively, as above.

Answer 3

This is probably pretty fast - just a few operations per denomination:

def change(amount):
    money = ()
    for coin in [25,10,5,1]
        num = amount/coin
        money += (coin,) * num
        amount -= coin * num

    return money

Answer 4

This problem could be solved pretty easy with integer partitions from number theory. I wrote a recursive function that takes a number and a list of partitions and returns the number of possible combinations that would make up the given number.

http://sandboxrichard.blogspot.com/2009/03/integer-partitions-and-wiki-smarts.html

It's not exactly what you want, but it could be easily modified to get your result.