Python: change calculator

Question

I am trying to calculate the number of quarters, dimes and nickles needed to sum to an amount of change with the least coins possible. Here is my code:

x = raw_input("Please enter an amount of change")
x = float(x)
q = .25
d = .1
n = .05
numberQ = x/q
numberQ = int(numberQ)
money2 = x - (numberQ * q)
numberD = money2/d
numberD = int(numberD)
money3 = money2 - (numberD * d)
numberN = money3/n
numberN = int(numberN)
print numberQ
print numberD
print numberN

The output is off. For example, if I enter 1.95 it will return 7 quarters, 1 dime and 1 nickel when it should be 7 quarters 2 dimes and 0 nickels.

protip: write a function which finds out how many $coins can be taken out of $total and returns $remainder — Phil Frost, Feb 19 '16 at 20:12
You might want to round all your integers down after dividing. — wrkyle, Feb 19 '16 at 20:14
It might round up. **Edit** I'm incorrect, python 2.7 `int` rounds towards zero. You're good. — wrkyle, Feb 19 '16 at 20:16
[Float arithmetic is imprecise](http://stackoverflow.com/questions/588004/is-floating-point-math-broken). Use integers and ask for cents instead of dollars (e.g. 195 instead of 1.95). Next time, use a debugger and run through your code to see what's going on. — Vincent Savard, Feb 19 '16 at 20:17
Finding the fewest coins possible is an application of [Dijkstra's Shortest Path Algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm). — Wolf, Feb 19 '16 at 20:18
It's not possible to represent fractions like .10 or .05 exactly in binary, which is what your computer uses. My suggestion would be to multiply the input by 100 to get the number of pennies and use whole numbers for all calculations. — kindall, Feb 19 '16 at 20:18

wrkyle · Answer 1 · 2016-02-19T22:04:54.183

The problem is in the second step. If you start with 1.95, step one returns 7 quarters with a remainder of $0.20. So money2 is now 0.20. Now we divide by the value of a dime. Because of floating point error our result is likely not an even 2 but more like 1.9999999. Python 2.7's int() method rounds towards zero so this gets rounded to 1 dime. The remainder is $0.10 and this gets divided by the value of a nickle which leads to the same problem but this time it rounds down to one nickle.

To fix this, I recommend using an integer number of pennies instead of a floating point value representing dollars.

So, 1.95 becomes 195 and the values of a quarter, a dime, and a nickle are 25, 10, and 5, respectively.

Edit Try this:

x = raw_input("Please enter an amount of change (in pennies)")
x = int(x)
q = 25
d = 10
n = 5
numberQ = (x - (x % q))/q
money2 = x % q
numberD = (money2 - (money2 % d))/d
money3 = money2 % d
numberN = (money3 - (money3 % n))/n
pennies = money3 % n
print numberQ
print numberD
print numberN
print pennies

The % gives the remainder of an integer division. If we subtract the remainder from the amount we started with and divide that by the coin value we know the result will be a whole integer. The remainder becomes the new amount of money.

Jeff · Answer 2 · 2016-02-19T22:24:53.153

It is due to float not precisely holding the values.

>>> money2/d
1.9999999999999996

Try multiplying everything by 100:

x = float(195)
q = float(25)
d = float(10)
n = float(5)
numberQ = x/q
numberQ = int(numberQ)
money2 = x - (numberQ * q)
numberD = money2/d
numberD = int(numberD)
money3 = money2 - (numberD * d)
numberN = money3/n
numberN = int(numberN)
print numberQ
print numberD
print numberN

Online Example

Edit: You could also use the decimal package to do this:

from decimal import Decimal
x = Decimal('1.95')
q = Decimal('.25')
d = Decimal('.10')
n = Decimal('.05')
numberQ = x/q
numberQ = int(numberQ)
money2 = x - (numberQ * q)
numberD = money2/d
numberD = int(numberD)
money3 = money2 - (numberD * d)
numberN = money3/n
numberN = int(numberN)
print numberQ
print numberD
print numberN

score 1 · Answer 3 · answered Feb 19 '16 at 20:25

You appear to be running into floating point precision errors; for example, after running your code in IDLE, requesting money2 and money3 gives these values:

>>> money2
0.19999999999999996
>>> money3
0.09999999999999995

Computerphile has a good video on this here, if you would like to learn more. Apart from that, try converting it so that money is represented by an integer number of cents; i.e. $1.95 would be 195.

Good luck.

score 0 · Answer 4 · edited Feb 19 '16 at 23:17

0

the problem is that your float value will sometime approximate the real value: In your example the value of money2 is suppose to be 0.2 but the value is maybe 0.1999999... so 0.1999999/0.10 = 1.9999999999 when you transform to int it will truncate and become 1 and not 2 like you want :

you can try to multiply by 100

x = x * 100
q = 25
d = 10
n = 5

Online Example

edited Feb 19 '16 at 23:17

wrkyle

529
1
13
36

answered Feb 19 '16 at 20:31

Mr Rubix

1,492
14
27

score 0 · Answer 5 · answered Oct 13 '19 at 16:24

I just had a similar problem and this seemed to work, its probably much longer than it needs to be:

EDIT: for this you are enter an integer - $78.65 is entered as 7865.

total = int(input())

if total == 0:
    print('no change')
if total//100 >= 1:
    if total//100 == 1:
        print(total//100, 'dollar')
        total = total % 100
    elif total//100 > 1:
        print(total//100, 'dollars')
        total = total % 100
if total//25 >= 1:
    if total//25 == 1:
        print(total//25, 'quarter')
        total = total % 25
    elif total//25 > 1:
        print(total//25, 'quarters')
        total = total % 25
if total//10 >= 1:
    if total//10 == 1:
        print(total//10, 'dime')
        total = total % 10
    elif total//10 > 1:
        print(total//10, 'dimes')
        total = total % 10
if total//5 >= 1:
    if total//5 == 1:
        print(total//5, 'nickel')
        total = total % 5
    elif total//5 > 1:
        print(total//5, 'nickels')
        total = total % 5
if total//1 >= 1:
    if total//1 == 1:
        print(total//1, 'penny')
    elif total//1 > 1:
        print(total//1, 'pennies')
else:
    total

Python: change calculator

5 Answers5