# CS50 Pset1 Greedy, change algorithm

The purpose of the code is to calculate the least amount of coins needed to produce correct amount of change given a dollar or cent user input. I'm just starting out and appreciate any pointers in how this code could/should be optimized.

The code works but I feel there is some redundancy with all those "while" loops. Using modulo math was another suggestion in order to solve the problem but I felt more comfortable using this solution for now.

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

int main (void)
{

// Variables//
float change;
int num = 0;
int quarter = 25;
int dime = 10;
int nickel = 5;
int penny = 1;

// Input of change//
do
{
printf("How much change is owed?  ");
change = get_float();
}
while (change <= 0);

printf("%.2f\n",change);

// conversion from dollars to cents (need to look over use of rounding)

int cents = (change * 100);

//Coin count//

while ( cents >= quarter)
{
cents -= quarter;
num++;
}

while (cents >= dime)
{
cents -= dime;
num++;
}

while (cents >= nickel)
{
cents -= nickel;
num++;
}

while (cents >= penny)
{
cents -=penny;
num++;
}

printf("%d\n", num);
}

• You should try proper indentation. That would make the code easier to read... – Deduplicator Jun 12 '17 at 23:20

## Be careful with that algorithm.

It looks pretty intuitive, but it would not work for some other coin values.

For example, if we need to deal 20 cents using coins of 17, 10 and 1, this greedy approach would give (17, 1, 1, 1) - 4 coins, whereas (10, 10) is just 2 coins.

Figuring out the difference - when your algorithm works and when it does not - would be an interesting exercise in itself.

## Wasteful loops

while ( cents >= quarter) {
cents -= quarter;
num++;
}


You can replace it with something like:

num += cents / quarter;
cents = cents % quarter;


Note that if you put coin values in array, this can be done in a loop.

Generally, your code would spend most of its time waiting for user to type the number and will give answer immediately, there's little point in optimisation.

You should adopt some code style though, your indentation is inconsistent. Indentation makes code structure more immediately apparent. I don't think it's a problem for you now, but it would be a problem for you on bigger assignments and it would be a problem for other people who would have to read (and grade) your code. Take a look at one of these if your course does not have one.

• Thanks a lot for the link regarding proper code structure. Regarding your concern about the code not working for some coin values I'm not sure I understand. If I would make the input that i owe 0.20c in change it gives me 2 in answer (10,10). – Ca84 Jun 13 '17 at 4:52
• @Ca84, change coin values from [25, 10, 5, 1] to [17, 10, 5, 1]. Does it give 2 or 4? Another example - make 6 cents from coins 4, 3 and 1. It's a well-known problem and I suppose later you'd have to solve the general case with dynamic programming. – Daerdemandt Jun 13 '17 at 8:32
• @Deardemandt, appreciate the clarification and the link. Great material for me that is just starting out and doing this on my spare time. – Ca84 Jun 13 '17 at 8:45
• @Ca84 if you're doing this on your own, I'd recommend going with some course to make sure your curriculum touches on all essential stuff. Coursera should have plenty of those, with the added benefit of forums where other students ask questions about the same material and teachers answer them. You can also try finding a buddy - you write the code, give it to buddy and he explains what he thinks your code does (and vice versa). If he's stumped with something - rewrite it to be more self-evident. You both will learn to read the code and write readable code this way. – Daerdemandt Jun 13 '17 at 9:12