Calculating smallest number of coins error

Question

I've recently started an online course in C, and am working through the second question in PS1. The question requires us to request an input of change from a user in dollars, and to calculate the smallest number of coins you can give them that change with, provided you are only allowed 25 cent, 10 cent, 5 cent and 1 cent coins.

For example 50 cents would be 2 25 cent coins, and 65 cents would be 2 25 cent coins, 1 10 cent coin and 1 5 cent coin.

Here is my code:

#include <stdio.h>
#include <cs50.h>

int main(void)
{
    float change = 0;
    int coinCounter = 0;
    int remainder = 0;
    int remainder1 = 0;
    int remainder2 = 0;
    int remainder3 = 0;
.
    do
    {
        printf("Please enter the change in dollars: ");
        change = GetFloat();
    }
    while(change <= 0);

    //converts amount in dollars to cents
    change = change*100;

    //We want to use the largest number of big cois as possible to make up the change.
    // This calculates the remainder (if any) after dividing the change by 25. % = modulo, only works with integer operands.
    remainder = (int)change % 25;

    //(change - remainder) gets us the largest number divisible by 25. This line then calculates 
    // the maximum number of 25cent coins we can use, and sets this number equal to the coinCounter.
    coinCounter = ((int)change - remainder)/25;

    //Finds the remainder (if any) when dividing the last remainder by 10.
    remainder1 = remainder % 10;

    //(remainder - remainder1) gets us the largest number divisible by 10. Dividing this by 10, we
    // determine the max amount of 10 cent coins we can use to make up the required change. We then add 
    // this number of coins to the total coinCounter.
    coinCounter = coinCounter + ((remainder - remainder1)/10);

    //Again, take the remainder (if any) from the last calculation, and find the remainder when dividing by 5.
    remainder2 = remainder1 % 5;

    // (remainder1 - remainder2)/5 tells us the number of 5 cent coins we need to make up the required change. 
    // We add the number of coins to the coin counter.
    coinCounter = coinCounter + ((remainder1 - remainder2)/5);

    //Finds the remainder when dividing last remainder by 1. There will actually be no remainder, so remainder 3 will
    // equal zero. 
    remainder3 = remainder2 % 1;

    //Here, (remainder2 - remainder1)/1 Finds the number of 1 cent coins required to make up the left change.
    // remainder3 will always be zero. Hence (remainder2)/1 will always be equal to remainder 2. We add this number
    // of 1 cent coins to the coinCounter.
    coinCounter = coinCounter + ((remainder2 - remainder3)/1);

    //We print out coinCounter, which is the smallest number of coins required to make up the change.
    printf("%i\n",coinCounter);
}

Now I am new to programming, so I am very aware that there are probably far more efficient ways of tackling this problem. However, this seems to work fairly well. However, strangely, I get an incorrect result when I try '4.2'. I should get 18 coins (16 25 cent coins and 2 10 cent coins), however the program displays 22. It works well for all other numbers I have tried however.

I cannot figure out what I have done wrong. I feel like it either has something to do with where I change dollars to cents by multiplying by 100, OR, where I calculate the modulo and cast change to an int, but I unfortunately cannot figure it out alone.

I have heavily annotated my code so it is somewhat easier to understand. I hope someone can help me with this!

Answer 1

I would do something simpler, like:

 int main(void)
{
    float change = 0;
    int coinCounter = 0;
    int remainder = 0;
    int remainder1 = 0;
    int remainder2 = 0;

do
{
    printf("Please enter the change in dollars: ");
    change = GetFloat();
}
while(change <= 0);

change = change*100;
coinCounter = (int)change/25; //number of 25cents
remainder = change % 25; //rest

if(remainder > 0){
     coinCounter += (int)remainder/10; //number of 10cts
     remainder1 = remainder%10;
}

if(remainder1 > 0){
     coinCounter += (int)remainder1/5; //number of 5cts
     remainder2 = remainder1%5
}

coinCounter += remainder2; //number of 1cts

printf("%i\n",coinCounter);   

}

Does it solve your problem with 4.2 ? I can't test right now.

Answer 2

The issue is that you have taken the change variable as a float, while all the other variables are ints.

The conversion of a float to an int introduces small unpredictable errors and can fail in some cases.

If you are interested in there is a very good article here.

I would suggest that you take the input as cents, or if that is not possible, take another integer variable and convert to cents at the start of the program and use that instead in the calculations.

Answer 3

As EOF has (rather snarkily) pointed out in their comment you are running into an issue with floating point numbers. Floating point numbers are a not perfect, there are many (infinitely many) numbers that can't be exacltly represented by a C float or double.

There's lots of good information on the web about this, for example here but the short explanation is that some decimal values when calculated in C using floats give the wrong answer and one such number is 4.2 * 100 in your particular compiler.

One possible solution in your case is to convert the float to a long, so something like:

change = change * 100 ;
long value = change >= 0 ? (long)(change+0.5) : (long)(change-0.5) ;

This should give you the exact number of cents and remove the small error in the floating calculation.

As an aside these effects can be dificult to see sometimes, try printing the result of this:

float x = 4.2 * 100 ;
float y = 4.2 ;
y = y * 100 ;

In my compiler this does result in 420 in x but 419.99... in y.

Answer 4

As others have pointed out, floating point values cannot always be represented perfectly. To address the error, you can round to the nearest integer. Here is a very simple function to start with:

int round(float number)
{
    return (number >= 0) ? (int)(number + 0.5) : (int)(number - 0.5);
}

Use it in your code like this:

int main(void)
{
    float change = 0;
    int changed = 0;
    int coinCounter = 0;
    int remainder = 0;
    int remainder1 = 0;
    int remainder2 = 0;
    int remainder3 = 0;

do
{
    printf("Please enter the change in dollars: ");
    change = GetFloat();
}
while(change <= 0);

//converts amount in dollars to cents
changed = round(change*100);//changes 419... to 420 etc.
...(more code)

You will have to experiment with corner cases to make it work well for all conditions, but this will get you started.

Note: this code example for rounding is over simplified, and provided just to get you started. The problem is really more complicated as illustrated by this conversation dealing with rounding floats to nearest integer value.