Bug in my code for greedy

Question

Here's my implementation of the algorithm:

initially declared the variables as, quarter = 0.25, dime = 0.10, nickel = 0.05, penny = 0.01

takes user input for the current balance
iteration while (balance - quarter >= 0)  
  subtract quarter from the balance  
  increase coin by one

iteration while (balance - dime >= 0)   
  subtract dime from the balance 
  increase coin by one

iteration while (balance - nickel >= 0)   
  subtract nickel from the balance   
  increase coin by one

iteration while (balance - penny >= 0)   
  subtract penny from the balance   
  increase coin by one

print the number of coins

Now the problem is that my answer is always a few coins less. I tried to debug it by placing various print statements and it turns out that my program doesn't enter the last while loop.

For example when I enter balance = 0.41, the first loop subtracts the amount 0.25, the second loop subtracts 0.10, the third loop subtracts 0.05 and at this point the balance is 0.01 which is greater than 0 but it doesn't enter the last loop. I tried manually subtracting penny from the balance 0.01 to get -0.0000.

Can anyone tell me what I'm doing wrong here? If this was python, it would have handled this issue on it's own.

Answer 1

Well, first of all, you should deal with ints because floats are not precise. You can round a float to an int using the function named round() that's declared in math.h. Run

man round

in the terminal for more information!

Don't forget that you should first convert dollars to cents by multiplying the amount in dollars by 100.

Second, you shouldn't be iterating while balance - quarter (dime, nickle or penny) >= 0. Here's the reason why

Given the number 42, this has a quarter, a dime, a nickle and two pennies.

  1 x 25
+ 1 x 10
+ 1 x 5
+ 2 x 2
--------
  42

What you're basically doing with your code is that you're iterating as long as the expression balance - quarter (or whatever) is >= 0. Meanwhile, as you we enter the loop

while (balance - quarter >= 0)

given 42 and balance and (assuming you're dealing with ints, 25 as quarter), your program will keep looping as long as balance >= 0.

  42 // >= 0? true
- 25
----
  17 // >= 0? true
- 25
----
- 8 // >= 0? false

Uh-oh! Now, we're getting into troubles!

What we should be doing is iterating as long as balance >= quarter (in the first loop). And similarly, for the dimes and nickles. In fact, following your approach, pennies don't need a loop at all since the balance that's remaining in pennies is equal to the number of pennies (the coins).