# Making change using the smallest possible number of coins

Posted on

Problem

I have written code based on the Greedy Algorithm. The example can be found here.

Problem: Make a change of a given amount using the smallest possible number of coins.

Coins available are:

1. dollars (100 cents)
2. quarters (25 cents)
3. dimes (10 cents)
4. nickels (5 cents)
5. pennies (1 cent)

This outputs an array of coins:

``````<?php

function makeChange(\$amount) {
\$c = array(100, 25, 10, 5, 1);
\$sol = array();
\$sum = 0;
\$i = 0;
\$ele = \$c['0'];
while (\$sum != \$amount) {
\$sum = \$sum + \$ele;
if (\$sum > \$amount) {
\$sum = \$sum - \$ele;
\$i++;
\$ele = \$c[\$i];
continue;
}
\$sol[] = \$ele;
}
return \$sol;
}

\$amount = 356;
\$sol = makeChange(\$amount);
print_r(\$sol);
?>
``````

Can this become more optimized?

Solution

The following is a bit of variation, exploiting that one does not need to subtract the same coin value one-by-one.

``````\$c = array(100, 25, 10, 5, 1); // \$coins
\$n = array(  0,  0,  0, 0, 0); // Number of coins.
\$i = 0;
while (\$amount > 0) {
\$k = floor(\$amount / \$c[\$i]); // How many coins
\$n[\$i] = \$k;
\$amount -= \$k * \$c[\$i];
// Or shorter: \$amount %= \$c[\$i];
++\$i;
}
``````

Also, I subtract from the original amount instead of adding to `\$sum`.