Integer overflow in greedy coin counting

Question

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

int main (void) { 

    printf ("Enter amount: ");
    float amount = GetFloat();
    int coins = 0;

    while (amount != 0) {

        if (fmod(amount, 0.25) == 0) {
            amount = amount - 0.25;
            coins += 1;
        }

        else if (fmod(amount, 0.10) == 0) {
            amount = amount - 0.10;
            coins += 1;
        }

        else if (fmod(amount, 0.05) == 0) {
            amount = amount - 0.05;
            coins += 1;
        }

        else {
            amount = amount - 0.01;
            coins += 1;
        }
    }

    printf ("Coins : %d\n", coins);
}

I'm trying to implement a small greedy algorithm, in which a user inputs an amount of money ( Ex: 9.25 ) and we output the least amount of coins that it takes for us to exchange it in change( 25 cents, 10 cents, 5 cents and 1 cent only).

This algorithm works with int amounts like 10 or 20 and with amounts that only requires the program to use the 25 cents coins.

If I try an amount like 9.10 or 9.01, I get a runtime error, signed integer overflow. I understand what it means, but I don't understand how can the value of coins go so high all of a sudden.

Answer 1

As Danial Tran said it is better to use int when you do logical operations. Please read Why not use Double or Float to represent currency? Also you can avoid while loop.

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

int main (void) { 

    printf ("Enter amount: ");
    //float amount = GetFloat(); //Please refer to chqrlie's comments below.
    double amount  = 0.0;
    scanf("%lf",&amount); //I don't know GetFloat() equivalent for double. So using scanf().

    long long int amountInt = (long long int) (amount * 100.0);

    int coins = 0;

    if (25 <= amountInt) {
        coins += (amountInt/25);
        amountInt = amountInt % 25;
    }

    if (10 <= amountInt) {
        coins += (amountInt/10);
        amountInt = amountInt % 10;
    }

    if (5 <= amountInt) {
        coins += (amountInt/5);
        amountInt = amountInt % 5;
    }

    if (1 <= amountInt) {
        coins += amountInt;
    }

    printf ("Coins : %d\n", coins);
}

Answer 2

This is because the computer represent the decimals in binary (power of 2)

For 0.25, the computer can represent it properly in binary. This is because we can obtain 0.25 exactly using power of 2's.

However for 0.10 ( or other denominations mentioned ), they cannot be expressed exactly in powers of 2.

Suppose you try to obtain 0.1 using power of 2's , you won't be able to obtain it exactly. You can just go near it.

0.1 = 0.0625 ( 2^4 ) + 0.03125 ( 2^5 ) + 0.00390625 ( 2^-8) +...

You will approach 0.1 , but you'll never reach 0.1 exactly.

Float, double everyone has a fixed number of bits to represent a decimal. So it will keep only those many bits, whose sum would be slightly less than 0.1

If you want to follow the same approach, you can have 2 possible solutions :-

1. Use (amount > 0) instead of (amount != 0), or
2. Use currencies which can be expressed easily in powers of 2 e.g. 0.25, 0.125 , 0.375 , 0.06125.

Answer 3

The main problem with your algorithm is invalid usage of fmod function. According to definition the result of fmod(num, denom) is

fmod = num - floor(num/denom) * denom

where floor(num/denom) is integer. Thus, fmod(9.10, 0.25) == 0.1, fmod(9.10, 0.10) == 0.1.

In addition, the manipulation with floating point number rarely gives exact results. so amount is never 0.

Answer 4

You cannot compute this with the float type. Amounts that are not exact multiples of 0.25 cannot be represented exactly in either the float or the double type.

You can fix this problem by computing an exact number of cents and dispatch it using integer arithmetics:

#include <stdio.h>
#include <math.h>

void print_coins(int coins, const char *singular, const char *plural) {
    if (coins > 0)
        printf(" %d %s", coins, coins > 1 ? plural : singular);
}

int main(void) {
    for (;;) {
        double amount;
        int amountInt, coins, quarters, dimes, nickels, pennies;

        printf("Enter amount: ");
        if (scanf("%lf", &amount) != 1 || amount <= 0)
            break;

        amountInt = (int)(amount * 100.0 + 0.5);

        quarters = amountInt / 25;
        amountInt %= 25;
        dimes = amountInt / 10;
        amountInt %= 10;
        nickels = amountInt / 5;
        amountInt %= 5;
        pennies = amountInt;
        amountInt = 0;

        coins = quarters + dimes + nickels + pennies;

        printf("coins returned: %d:", coins);
        print_coins(quarters, "quarter", "quarters");
        print_coins(dimes, "dime", "dimes");
        print_coins(nickels, "nickel", "nickels");
        print_coins(pennies, "penny", "pennies");
        printf("\n");
    }
    return 0;
}

Notes:

• Using float without the + 0.5, the change is incorrect for as little as 100.10: one penny short.
• Using float, the change is incorrect for 1000000.10: 3 extra pennies.
• To handle amounts above 20 million dollars, you need a larger integral type such as long long int. With that, you can handle amounts exceeding the US national debt.

Answer 5

It seems that no one has answered the particular question

If i try an amount like 9.10 or 9.01, i get a runtime error,signed integer overflow, i understand what it means, but i don't understand how can the value of coins go so high all of a sudden.

so for the sake of completeness, partially as an exercise:

You can find the reason using a debugger. I copied your code and found that it runs for very long. Interrupting it a moment after start revealed that the code freezes repeating this check:

if (fmod(amount, 0.25) == 0) {
    amount = amount - 0.25;
    coins += 1;
}

At the moment of the interruption amount was about minus 1.2 million and coins almost 5 million. This clearly shows one thing you failed to check: negativity. It can happen easily with floats that you miss the exact zero, as the others have correctly reasoned, no need to repeat that. But if that happens, your program should get worried the moment amount gets negative. Otherwise, under the right conditions, it may as well keep subtracting its way towards negative infinity, and yes, integer overflow will happen in coins.

Answer 6

Your algorithm is not correct:

For example with 30 cents you can exchange to: 25+5 (2 coins) with your algorithm it would be 10+10+10 (3 coins). So greedy means why it's greater than 25 cents then exchange to 25 cents first.

while (amount != 0) {

    if (amount >= 0.25) {
        amount = amount - 0.25;
        coins += 1;
    }

    else if (amount >= 0.10) {
        amount = amount - 0.10;
        coins += 1;
    }

    else if (amount >= 0.05) {
        amount = amount - 0.05;
        coins += 1;
    }

    else {
        amount = amount - 0.01;
        coins += 1;
    }
}

If you want to do that way.

Better way:

int coinTypes[] = {0.25, 0.1, 0.05, 0.01};

for (int i = 0; i < 4; i++) {
   coins += floor(amount / coinTypes[i];
   amount -= coins * coinsTypes[i];
}