# Harvard CS50 Problem Set 1: greedy change-making algorithm

The goal of this code is to take dollar or cents input from the user and give out minimum number of coins needed to pay that between quarters, dimes, nickels and pennies. If this code can be shortened, how would one do it?

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

int main(void)
{
float b;
do
{
b = GetFloat();
}
while (b<0);

int v;
int q = 25;
int d = 10;
int n = 5;
int p = 1;
int count=0;

b=b*100;
int c=round(b);
int balance = c;
printf("%i\n", balance);
//printf("%.2f\n", round(c));

while(balance>=q)
{
v=balance/q;
count=count+v;
balance=balance-(q*v);
}
while(balance>=d)
{
v=balance/d;
count=count+v;
balance=balance-(d*v);
}
while(balance>=n)
{
v=balance/n;
count=count+v;
balance=balance-(n*v);
}
while(balance>=p)
{
v=balance/p;
count=count+v;
balance=balance-(p*v);
}

printf("the number of coins needed is: %i\n", count);
printf("balance after coins paid: %i\n", balance);

}

• there is also the $.50,$1.00, \$20.00 and perhaps some other coin denominations that I skipped. I would not discount these other coin denominations (although most of them are rarely seen outside of places like Reno NV. and Los Vegas NV. Commented Feb 3, 2015 at 3:03
• @user3629249 - it's "Las" Vegas. You're probably confusing it with its sister city, Lost Wages. Commented Feb 3, 2015 at 12:23

The first thing that sticks out to me is indentation. But I'm going to recommend some other changes, so I'll address indentation last.

Let's give our variables some better, more descriptive names, and let's declare our constants as constants. And since we're taking in a floating point number for input from the user, we need to compare that with other floating point numbers. Or we need to use it as an integer.

int const kVALUE_QUARTER = 25;
int const kVALUE_DIME = 10;
int const kVALUE_NICKEL = 5;
int const kVALUE_PENNY = 1;

float userInput = -1.0;
int balance = 0;
int coinCount = 0;

do {
userInput = GetFloat();
} while (userInput < 0);

balance = (int)(userInput * 100.0);


Now, we can eliminate all of our loops using the modulo operator (%) and integer division.

// number of quarters:
coinCount += balance / kVALUE_QUARTER;
balance %= kVALUE_QUARTER;

// number of dimes:
coinCount += balance / kVALUE_DIME;
balance %= kVALUE_DIME;

// number of nickels:
coinCount += balance / kVALUE_NICKEL;
balance %= kVALUE_NICKEL;

// number of pennies:
coinCount += balance / kVALUE_PENNY;
balance %= kVALUE_PENNY;


Now let's put it all together and take a look at our indentation:

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

int main(void) {
int const kVALUE_QUARTER = 25;
int const kVALUE_DIME = 10;
int const kVALUE_NICKEL = 5;
int const kVALUE_PENNY = 1;

float userInput = -1.0;
int balance = 0;
int coinCount = 0;

do {
userInput = GetFloat();
} while (userInput < 0);

balance = (int)(userInput * 100.0);

// number of quarters:
coinCount += balance / kVALUE_QUARTER;
balance %= kVALUE_QUARTER;

// number of dimes:
coinCount += balance / kVALUE_DIME;
balance %= kVALUE_DIME;

// number of nickels:
coinCount += balance / kVALUE_NICKEL;
balance %= kVALUE_NICKEL;

// number of pennies:
coinCount += balance / kVALUE_PENNY;
balance %= kVALUE_PENNY;

printf("the number of coins needed is: %i\n", count);
printf("balance after coins paid: %i\n", balance);
}

• const int VALUE_QUARTER = 25; would be more idiomatic. The Hungarian k is pointless. Commented Feb 3, 2015 at 2:30
• @200_success is probably correct. I'm not a C-programmer. We tend to always use the k prefix in Objective-C. Commented Feb 3, 2015 at 2:31

// number of quarters:
coinCount += balance / kVALUE_QUARTER;
balance %= kVALUE_QUARTER;


And we can abstract this a little bit.

Let's write a function.

int coinsInBalance(int * balance, int coinValue) {
int coinCount = balance / coinValue;
balance %= coinValue;
return coinCount;
}


Now, we can replace our repeated blocks with the following:

coinCount += coinsInBalance(&balance, kVALUE_QUARTER);
coinCount += coinsInBalance(&balance, kVALUE_DIME);
coinCount += coinsInBalance(&balance, kVALUE_NICKEL);
coinCount += coinsInBalance(&balance, kVALUE_PENNY);

• cool. its good to see how a function would work in this situation in advance. I haven't started that lecture yet, so will definitely revisit this. Commented Feb 3, 2015 at 2:48

Why make this more complicated than it has to be?

#include <stdio.h>

void change(int cents)
{
int q, d, n, p;

q = cents / 25;
d = (cents - (q * 25)) / 10;
n = ((cents - (q * 25) - (d * 10)) / 5);
p = cents - (q * 25) - (d * 10) - (n * 5);

printf("cents : %d --> quarters %d  dimes %d  nickels %d  pennies %d\n",
cents, q, d, n, p);
}

int main(int argc, char **argv)
{
char str[1000];
int cents;

while(1)
{
fgets(str, 1000, stdin);

cents = atoi(str);
change(cents);
}
}


It's possible to eliminate all the temp variable declarations and just compute the values as we go:

void change(int cents)
{
printf("cents : %d --> quarters %d  dimes %d  nickels %d  pennies %d\n",
cents,
(cents / 25),
(cents - ((cents / 25) * 25)) / 10,
((cents - ((cents / 25) * 25) - ((((cents - ((cents / 25) * 25)) / 10) * 10))) / 5),
cents - (((cents / 25) * 25) +
(((cents - ((cents / 25) * 25)) / 10) * 10) +
(((cents - ((cents / 25) * 25) - ((((cents - ((cents / 25) * 25)) / 10) * 10))) / 5) * 5)));
}


but this way lies madness. :-)

Share and enjoy.

• "This way madness lies", so why suggest it then? You've effectively obfuscated the code and that does not make for a good answer here. Commented Feb 3, 2015 at 13:41
• The 1st chunk of code is good, the 2nd is "madness" as you say, a joke - just get rid of it so you can get some upvotes. Commented Feb 3, 2015 at 13:52
• "Why suggest it?" - to provide an example of what happens when good practices are ignored. Sometimes the negative example is useful to who why we do The Right Thing. And in my experience a touch of humor helps the lesson go down. YMMV. Commented Feb 3, 2015 at 14:03