# 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 <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. • 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. – Emily L. Jun 15 '15 at 15:34 • In your solution, why do you include paper money when the question asks only for quarters, dimes, nickels, and pennies? – user2023861 Jun 15 '15 at 18:17 • 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. – Brandon Jun 15 '15 at 18:31 • 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? – JS1 Jun 15 '15 at 19:42 • 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. – Brandon Jun 15 '15 at 20:01 ## 2 Answers ## 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);
}

• Wow far more than I could have ever asked for! Thank you so much! – Brandon Jun 15 '15 at 21:10

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].

• 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! – Brandon Jun 15 '15 at 16:34
• I don't understand so many downvotes, i just gave an alternative algoritmh and the OP is fine with it... – Caridorc Jun 17 '15 at 8:22
• No worries I'm not sure why either. – Brandon Jun 17 '15 at 14:22
• @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. – Malachi Jun 30 '15 at 13:59
• I must have hit the upvote twice because I did when he initially wrote the post intend to upvote it. – Brandon Jun 30 '15 at 14:14