# Greedy algorithms to find minimum number of coins (CS50)

I'm taking CS50, an Introduction to CS, and we're asked to do the following task:

Suppose that a cashier owes a customer some change and in that cashier’s drawer are quarters (25¢), dimes (10¢), nickels (5¢), and pennies (1¢). The problem to be solved is to decide which coins and how many of each to hand to the customer. Think of a “greedy” cashier as one who wants to take the biggest bite out of this problem as possible with each coin they take out of the drawer. For instance, if some customer is owed 41¢, the biggest first (i.e., best immediate, or local) bite that can be taken is 25¢. (That bite is “best” inasmuch as it gets us closer to 0¢ faster than any other coin would.) Note that a bite of this size would whittle what was a 41¢ problem down to a 16¢ problem, since 41 - 25 = 16. That is, the remainder is a similar but smaller problem. Needless to say, another 25¢ bite would be too big (assuming the cashier prefers not to lose money), and so our greedy cashier would move on to a bite of size 10¢, leaving him or her with a 6¢ problem. At that point, greed calls for one 5¢ bite followed by one 1¢ bite, at which point the problem is solved. The customer receives one quarter, one dime, one nickel, and one penny: four coins in total

Here is my solution to the problem:

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

float cents, money;
int dollars_to_cents(int dollars);
int get_max_coins(int _cents, int coin_type);
int min_coins_exchanged(int _money, int _coin_types[], int _arr_length);
int quarter = 25, dimes = 10, nickles = 5, pennies = 1;

int main(void)
{
int arr_length = 4;
int coin_types[] = {quarter, dimes, nickles, pennies};
printf("%i\n", min_coins_exchanged(money, coin_types, arr_length));
}

// Given some amount of money, this returns the maximum amount of coins of a certain type possible
// such that the remaining money is less than the value of the coin type, then it subtracts our money by that amount
int get_max_coins(int _cents, int coin_type)
{
int max_coins = floor((float)((_cents) / coin_type));
money -= max_coins * coin_type;
return max_coins;
}

{
do
{
money = get_float("Change owed: ");
}
while (money < 0);
return money;
}

// Necessary to avoid problems with floating point imprecision
int dollars_to_cents(int dollars)
{
return round(money * 100);
}

// Calculates the minimum amount of coins exchanged such that when these coins are added up they are equal to the change owed
int min_coins_exchanged(int _money, int _coin_types[], int _arr_length)
{
int _min_coins_exchanged = 0;
for(int i = 0; i < _arr_length; i++)
{
_money = money;
_min_coins_exchanged += get_max_coins(_money, _coin_types[i]);
}
return _min_coins_exchanged;
}


I'm looking for feedback on my code. How do I make my code better and cleaner? I.e in terms of readability, performance, comments, design principles, etc. There's a lot of ways to approach this problem, and indeed when trying to solve it I've tried many different ways but this is my current favorite. What do you think about my solution? Perhaps there's a better way to approach the problem?

This code needs compiling with more warnings enabled:

gcc -std=c17 -fPIC -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds  -Wstrict-prototypes    -Wconversion    254841.c    -o 254841
254841.c: In function ‘main’:
254841.c:14:13: warning: conversion from ‘int’ to ‘float’ may change value [-Wconversion]
^~~~~~~~~~~~~~~~
254841.c:17:40: warning: conversion from ‘float’ to ‘int’ may change value [-Wfloat-conversion]
printf("%i\n", min_coins_exchanged(money, coin_types, arr_length));
^~~~~
254841.c: In function ‘get_max_coins’:
254841.c:24:21: warning: conversion from ‘double’ to ‘int’ may change value [-Wfloat-conversion]
int max_coins = floor((float)((_cents) / coin_type));
^~~~~
254841.c:25:11: warning: conversion from ‘int’ to ‘float’ may change value [-Wconversion]
money -= max_coins * coin_type;
^~
254841.c:36:12: warning: conversion from ‘float’ to ‘int’ may change value [-Wfloat-conversion]
return money;
^~~~~
254841.c: In function ‘dollars_to_cents’:
254841.c:42:12: warning: conversion from ‘double’ to ‘int’ may change value [-Wfloat-conversion]
return round(money * 100);
^~~~~~~~~~~~~~~~~~
254841.c:40:26: warning: unused parameter ‘dollars’ [-Wunused-parameter]
int dollars_to_cents(int dollars)
~~~~^~~~~~~
254841.c: In function ‘min_coins_exchanged’:
254841.c:51:18: warning: conversion from ‘float’ to ‘int’ may change value [-Wfloat-conversion]
_money = money;
^~~~~


You have avoided some of the common traps, such as embedding the set of coins into the logic, although I wouldn't give those locale-specific names - here in Britain, we have 1, 2, 5, 10, 20, 50, 100 and 200 but they don't have nicknames.

I would instead make the set of coins be a global constant, without naming them individually:

const unsigned int coin_values = {
25,  /* quarter */
10,  /* dime    */
5,   /* nickel  */
1    /* penny   */
};
const size_t coin_values_len = sizeof coin_values / sizeof *coin_values;


Avoid using floating-point types for money. The problem is that .01 is not an exact fraction in binary, so the code is prone to error due to rounding.

unsigned int dollars, cents = 0;
if (scanf("%u.%u") < 1) {
fputs("Currency parse failure\n", stderr);
return EXIT_FAILURE;
}
/* if we got here, we read the dollars, and perhaps the cents */
unsigned int total_cents = 100 * dollars + cents;  /* TODO: deal with overflow */


You're using some names that you shouldn't:

int get_max_coins(int _cents, int coin_type)


All identifiers beginning with _ followed by a letter are reserved for use by the implementation. That means it's a bad idea to use these names in your own code. There's no reason not to just call the argument cents without that prefix, so that's what I'd recommend.

There's some pointless conversion here:

int max_coins = floor((float)((_cents) / coin_type));


cents / coin_type is of type int. We convert that to float (losing precision), truncate the fractional part (which will be zero, since we started with an integer) and then implicitly convert to int. That code is a very inefficient and problematic way to write

int max_coins = _cents / coin_type;


There's some serious problems with global variables, and there seems to be confusion passing values by parameter or via globals. Look at this:

float money;

int main(void)
{
}

int dollars_to_cents(int dollars)
{
return round(money * 100);
}

{
do
{
money = get_float("Change owed: ");
}
while (money < 0);
return money;
}


In main(), we assign to money, which we're also using in ask_money. And dollars_to_cents() completely ignores its argument and shares the global variable. There's no need for this variable to be shared - each function can have its own local variable:

int main(void)
{
}

int dollars_to_cents(float dollars)
{
/* don't actually use float - see earlier in review */
return round(dollars * 100);
}

{
float money;
do
{
money = get_float("Change owed: ");
}
while (money < 0);
return money;
}


# Summary

• Eliminate the global variables
• Use more appropriate numeric types