Minimum number of coins to make change

Question

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 <stdio.h>
#include <cs50.h>
#include <math.h>
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);
 // Get the Dollars from the Float
 int getDollars = money;
 // Get the cents from the Float
 float getCents = roundf((money * 100) - (getDollars * 100));
 int convertCents = getCents;
 // Greedy Algorithm for Dollars
 int getHundreds = getDollars / 100;
 int getFifties = ((getDollars) - (100 * getHundreds)) / 50;
 int getTwenties = ((getDollars) - (50 * getFifties) - (100 * getHundreds)) / 20;
 int getTens = ((getDollars) - (20 * getTwenties) - (50 * getFifties) - (100 * getHundreds)) / 10;
 int getFives = ((getDollars) - (10 * getTens) - (20 * getTwenties) - (50 * getFifties) - (100 * getHundreds)) / 5;
 int getOnes = ((getDollars) - (10 * getTens) -(5 * getFives) - (20 * getTwenties) - (50 * getFifties) - (100 * getHundreds)) / 1;
 //Greedy Algorithm for Cents
 int getQuaters = convertCents / 25;
 int getDimes = ((convertCents) - (getQuaters * 25)) / 10;
 int getNickles = ((convertCents) - (getQuaters * 25) - (getDimes * 10)) / 5; 
 int getPennies = ((convertCents) - (getQuaters * 25) - (getDimes * 10) - (getNickles * 5)) / 1;
 printf("\n");
 if (convertCents == 0)
 {
 printf("The least possible steps you can make change from $%i.%i0 is %i. \n", getDollars, convertCents, (getHundreds + getFifties + getTwenties + getTens + getFives + getOnes + getQuaters + getDimes + getNickles + getPennies));
 }
 else if (convertCents < 10 && convertCents > 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.

• Emily L.: I don't have time to write an exhaustive review but I'll leave this as a comment: Never ever use floating point types for monetary values.
• user2023861: In your solution, why do you include paper money when the question asks only for quarters, dimes, nickels, and pennies?
• Brandon: Good question. On iTunes University (through iTunes for OS X) the content is not laid out very well(This is not the case for the iTunes University App on iOS devices). So initially I was having a hard time finding the requirements and rubric for this assignment. Secondly, I thought this would be closer to a real world example. A cashier wouldn't give out a 100 dollars worth of quarters, so it seemed weird for me to try and create a program that would do this.
• JS1: Perhaps you could tell us what you have learned so far, so we can better understand the limitations of your program. For example, have you learned about functions yet? Arrays? Structures?
• Brandon: I understand a function to be a way in which you can write code that you would like to be repeated in a segment of code that can be called to reduce redundancy. I am a little cloudy as to how to set them up in C, because I haven't gotten that far. An array is a variable that can hold multiple values of the same type in C, i think. I do kind of understand other concepts, but as in my experience with trying to learn languages the hardest part for me is know when to use a certain code construct. I understand: do while, for, if, and ternary statements pretty well as far as flow control goes.

Answer 1

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:

1. I added my own GetFloat() function because I don't have whatever library you are using.
2. I removed the use of roundf() and just did the rounding myself.
3. 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 <stdio.h>
#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);
}

• Brandon: Wow far more than I could have ever asked for! Thank you so much!

Answer 2

You should use a loop, the algorithm I suggest is this:

def minimum_coins (amount, coins):
 coins_used = []
 while amount:
 coin = max(c for c in coins if amount >= c)
 amount -= coin
 coins_used.append(coin)
 return len(coins_used)

of course translating this into low level C won't be short, but for sure shorter and more understandable than your implementation.

Let me make an example of my greedy algorithm, take the biggest possible coin each time:

How do I pay 117 cents using only [100, 20, 10, 5, 1] ?

1. 117 - 100 = 17
2. 17 - 10 = 7 # 100 and 20 would be too big
3. 7 - 5 = 2 # 100, 20 and 10 would be too big
4. 2 - 1 = 1
5. 1 - 1 = 0

Using five coins, namely [100, 10, 5, 1, 1].

• Brandon: I genuinely appreciate that advice. I kind of get the gist of your function. That being said you are using a lot of things I haven't learned yet. Im trying to stuck within what would have been learned in the first week. This is helpful though!
• Caridorc: I don't understand so many downvotes, i just gave an alternative algoritmh and the OP is fine with it...
• Brandon: No worries I'm not sure why either.
• Malachi: @Brandon, hasn't upvoted your post Caridorc. and from what the comment says, you are using tools from a toolbox that the OP doesn't have. it looks like you are giving OP a good Algorithm in the Second part of your answer though. there are no upvotes on this answer yet.
• Brandon: I must have hit the upvote twice because I did when he initially wrote the post intend to upvote it.