Minimum number of coins to make change

I am new to programming and I am taking CS50 2014 online through iTunes University. This is the change-making problem in Problem Set 1:


Write a program that first asks the user how much change is owed and then spits out the minimum number of coins with which said change can be made. Assume that the only coins available are quarters (25¢), dimes (10¢), nickels (5¢), and pennies (1¢).

I am pretty sure that my code is super "hacky." I would love understandable input on how I could have made a better algorithm or how I should have broken down the problem or "You did 'x' here"..."it would be better if you did 'y'."

#include 
#include 
#include 

int main(void)
{

    // declare float
    float money;

    // Get user input and check if input is positive
    do
    {
        printf("Please input the some amount of money you would like to make change for:  \n");
        money = GetFloat();
    } while (money  0)
    {
        printf("The least possible steps you can make change from $%i.0%i is %i. \n", getDollars, convertCents, (getHundreds + getFifties + getTwenties + getTens + getFives + getOnes + getQuaters + getDimes + getNickles + getPennies));
    }
    else
    {
        printf("The least possible steps you can make change from $%i.%i is %i. \n", getDollars, convertCents, (getHundreds + getFifties + getTwenties + getTens + getFives + getOnes + getQuaters + getDimes + getNickles + getPennies));
    }
}

Also please forgive me I kind of went out of the scope of the problem. I appended it knowing the fact that I would like to use currently circulating paper denominations as well as coins.

Printf format

I noticed that at the end of your program you had 3 cases due to trying to print the number of cents out correctly. You can do it all in 1 case by using the %02i format. This format prints an integer with 2 digit width and pads the leading digits with zeros.

Simplifying the logic

Right now, your logic for each denomination gets more and more complicated as you go along because you are subtracting more and more things from the total on each step. If you simply subtracted the amount from the total right away, you wouldn't have to repeat it on each step. For example:

int getHundreds = getDollars / 100;
getDollars -= getHundreds * 100;
int getFifties = getDollars / 50;
getDollars -= getFifties * 50;
int getTwenties = getDollars / 20;
getDollars -= getTwenties * 20;
// etc.

Using functions

Now that you have simplified the logic, you can put that logic into a function. For example:

/**
 * @param        pAmount          Points to amount of money.  Returns the amount
 *                                minus the amount used up by this denomination.
 * @param        denomination     The value of this denomination.
 * @return                        The number of units of this denomination.
 */
int makeChange(int *pAmount, int denomination)
{
    int ret = *pAmount / denomination;

    *pAmount -= ret * denomination;
    return ret;
}

int main(void) {
    // ...
    int remainingDollars = getDollars;
    int getHundreds = makeChange(&remainingDollars, 100);
    int getFifties  = makeChange(&remainingDollars,  50);
    int getTwenties = makeChange(&remainingDollars,  20);
    // etc.
}

Reducing the number of variables

Since you aren't actually printing out how many of each bill/coin you are using, you don't need so many variables. You only actually need to know how many bills plus coins you need. So you could change your code to:

int remainingDollars  = getDollars;
    int numBillsPlusCoins = 0;

    numBillsPlusCoins += makeChange(&remainingDollars, 100);
    numBillsPlusCoins += makeChange(&remainingDollars,  50);
    numBillsPlusCoins += makeChange(&remainingDollars,  20);
    // etc.

Using arrays

There's still a lot of repetition. It would be nice to not have to copy/paste one line per denomination. You can use arrays to handle each denomination in a loop instead. You just need to create an array with the possible bill denominations and one for the coin denominations.

Some other miscellany:

• I added my own GetFloat() function because I don't have whatever library you are using.

• I removed the use of roundf() and just did the rounding myself.

• I used a DIM() macro which returns the dimensions of a given array. You will encounter this in C a lot for loops which need to loop over a statically defined array.

Here is the final code:

#include 

#define DIM(array)        (sizeof(array)/sizeof(array[0]))

float GetFloat(void)
{
    float ret = 0;
    scanf("%f", &ret);
    return ret;
}

/**
 * @param       pAmount         Points to amount of money.  Returns the amount
 *                              minus the amount used up by this denomination.
 * @param       denomination    The amount for this denomination.
 * @return                      The number of units of this denomination.
 */
int makeChange(int *pAmount, int denomination)
{
    int ret = *pAmount / denomination;

    *pAmount -= ret * denomination;
    return ret;
}

int main(void)
{
    // declare float
    float money;
    const int billDenominations[] = { 100, 50, 20, 10, 5, 1 };
    const int coinDenominations[] = { 25, 10, 5, 1 };

    // Get user input and check if input is positive
    do
    {
        printf("Please input the some amount of money you would like to "
                "make change for:  \n");
        money = GetFloat();
    } while (money < 0);

    // Get the Dollars from the Float
    int numDollars = (int) money;

    // Get the cents from the Float (rounded to nearest cent)
    int numCents = (int) ((money - numDollars) * 100 + 0.5f);

    int remainingDollars = numDollars;
    int remainingCents   = numCents;
    int numBillsAndCoins = 0;

    // Greedy Algorithm for Dollars
    for (int i = 0;i < DIM(billDenominations);i++)
        numBillsAndCoins += makeChange(&remainingDollars, billDenominations[i]);

    // Greedy Algorithm for Cents
    for (int i = 0;i < DIM(coinDenominations);i++)
        numBillsAndCoins += makeChange(&remainingCents, coinDenominations[i]);

    printf("\nThe least possible steps you can make change from "
            "$%i.%02i is %i. \n", numDollars, numCents, numBillsAndCoins);
}

StackExchange Code Review Q#93651, answer score: 5