Give change using optimal denominations *considering that using descending units might not result in a correct result

Question

I'm struggling to solve a problem regarding a programming challenge:

• Rules:
  The cash register only has $2, $5, and $10 bills. Your algorithm should determine the best way to give change for any amount, using the fewest bills possible.

• Tests:
  Your solution should include tests (unit or otherwise) covering the scenarios provided in the examples, as well as for the specific amounts of $10, $11, $21, $23, and $31.

  A few test inputs and the expected optimized results in plain English:

  $10: one $10 bill
  $11: one $5, three $2 bills 
  $21: one $10, one $5, three $2 bills
  $23: one $10, one $5, four $2 bills
  $31: two $10, one $5, three $2 bills
  

My coding attempt has a few flaws such as non-positive quantities of bills, inelegant handling of unsatisfiable amounts, and incorrect results for amounts like $23 and $31: (Demo)

function rendreMonnaie(int $montant)
{
    //Déclaration des variables
    $listeBillets = [10, 5, 2];  //Liste des coupure dispo
    $nbEntree = 0; //Combien de fois un chiffre entre dans le montant
    $message = [];
    $reste = 0;
    $result = 0;


    for ($ibillet = 0; $ibillet < sizeof($listeBillets); $ibillet++) {
        // Calcul du reste de la division du montant par le billet
        $reste = $montant % $listeBillets[$ibillet];
        if ($reste == 0) {
            // Si le reste est 0, le montant est un multiple du billet
            // Calcul du nombre de billets nécessaires
            $nbEntree = intdiv($montant, $listeBillets[$ibillet]);
            // Ajout du nombre de billets et du type de billet au message
            array_push($message, "$nbEntree x $listeBillets[$ibillet]");
            break;
        } else if ($reste >= $listeBillets[2]) {
            // Si le reste est supérieur ou égal au plus petit billet
            // Calcul du nombre de billets nécessaires
            $nbEntree = intdiv($montant, $listeBillets[$ibillet]);
            // Ajout du nombre de billets et du type de billet au message
            array_push($message, "$nbEntree x $listeBillets[$ibillet]");
            // Mise à jour du montant avec le reste
            $montant = $reste;
        } else {
            if ($listeBillets[$ibillet] == 2) { 
               $nbEntree = intdiv($result, $listeBillets[$ibillet]);
               array_push($message, "$nbEntree x $listeBillets[$ibillet]");
            } else {
                $result = $montant - $listeBillets[$ibillet];
                $reste = $reste % $listeBillets[$ibillet];
                // Calcul du nombre de billets nécessaires
                $nbEntree = intdiv($result, $listeBillets[$ibillet]);
                array_push($message, "$nbEntree x $listeBillets[$ibillet]");
            }
        }
    }
    // Affichage du tableau message pour le débogag
    for ($i = 0; $i < sizeof($message); $i++) {
        // Suppression des éléments du message qui commencent par un nombre inférieur à 1
        if ($message[$i][0] < 1) {
            unset($message[$i]);
        }
    }
    // Conversion du tableau message en une chaîne de caractères
    $message = implode(" + ", $message);
    echo ($message);
}

Answer 1

I came up with a solution, but it's by no means optimal (especially when the target amount becomes rather large). First let's define a class that contains a collection of multiple denominations that might contain a solution to the problem.

class ChangeCollection
{
    public function __construct(protected array $denominations = [])
    {
    }

    public function getTotal()
    {
        return array_sum($this->denominations);
    }

    public function getDenominationsString()
    {
        sort($this->denominations);
        return implode(' ', $this->denominations);
    }

    public function addDenominations(array $denominations): array
    {
        return array_map(
            fn (int $denomination) => new ChangeCollection([...$this->denominations, $denomination]),
            $denominations
        );
    }
}

Now, we define a class that actually builds combinations of ChangeCollection objects and checks if it contains the actual solution.

class ChangeCalculator
{
    protected const DENOMINATIONS = [2, 5, 10];

    public function calculate(int $target): ChangeCollection
    {
        $collections = [new ChangeCollection];
        do {
            $collections = array_filter(array_merge(...array_map(
                fn (ChangeCollection $collection) => $collection->addDenominations(self::DENOMINATIONS),
                $collections
            )), fn (ChangeCollection $collection) => $collection->getTotal() <= $target);

            foreach ($collections as $collection) {
                if ($collection->getTotal() === $target) {
                    return $collection;
                }
            }
        } while (count($collections) > 0);

        throw new Exception("There is no possible combination of denominations.");
    }
}

You can now get the string with the outcome with following code:

$calculator = new ChangeCalculator;
echo $calculator->calculate(23)->getDenominationsString();

Answer 2

I kept my solution quite simple. First I started with creating two function that can add and remove bills from a simple array, and one function to sum the bills in that array:

function addBills(&$change, $value, $count)
{
    $change = array_merge($change, array_fill(0, $count, $value));
}

function removeBill(&$change, $value)
{
    $key = array_search($value, $change);
    if ($key !== false) {
        unset($change[$key]);
    }
}

function getChangeTotal($change)
{
    return array_sum($change);
}

These helper functions come in handy to keep track of what I'm doing in the function that computes the minimal number of bills to return:

function findMinimum($bills, $wantedTotal, $change = [])
{
    // without bills there's nothing to do
    if (count($bills) == 0) {
        return $change;
    }    
    // get the next smaller bill 
    $value = array_pop($bills);
    // how many of those will fit?
    $count = intdiv($wantedTotal - getChangeTotal($change), $value);
    if ($count > 0) {
        // add as many bills as will fit
        addBills($change, $value, $count);
        while ($count > 0) { 
            // can we find more change?
            $change = findMinimum($bills, $wantedTotal, $change);
            // did we reach the wanted total?
            if ($wantedTotal == getChangeTotal($change)) {
                return $change;
            } else {    
                // we have to use smaller bills
                $count--;
                removeBill($change, $value);
            }    
        }                                  
    }
    // try a smaller bill
    return findMinimum($bills, $wantedTotal, $change);
}

$bills = [2, 5, 10];

print_r(findMinimum($bills, 23));

This is a recursive function. The comments try to explain what it does. The result is:

Array
(
    [0] => 10
    [1] => 5
    [2] => 2
    [3] => 2
    [4] => 2
    [5] => 2
)

I did not create a nice output message, but this shouldn't be hard to do.

For a live demo see: https://3v4l.org/TCRIA

Answer 3

I am attracted to the elegance of a recursive approach for this task because by iterating the denominations in a descending order, you don't need to keep track of the most efficient path -- just halt the recursion upon encountering the first qualifying set.

Code with a range of tests: (Demo)

function optimalChange(int $amount, array $denominations): ?array {
    if (!$amount) {
        return []; // happy ending
    }

    foreach ($denominations as $d) {
        if ($d <= $amount) {
            $deeper = optimalChange($amount - $d, $denominations);
            if ($deeper !== null) {
                $result = array_merge([$d], $deeper);
                break; // run up the recursive branch
            }
        }
    }
    return $result ?? null;
}

$denominations = [10, 5, 2]; // must be rsort()ed at declaration
foreach (range(0, 35) as $target) {
    printf(
        "%s: %s\n",
        $target,
        json_encode(
            optimalChange($target, $denominations)
            ?: 'Sorry'
        )
    );
}

Output:

0: "Sorry"
1: "Sorry"
2: [2]
3: "Sorry"
4: [2,2]
5: [5]
6: [2,2,2]
7: [5,2]
8: [2,2,2,2]
9: [5,2,2]
10: [10]
11: [5,2,2,2]
12: [10,2]
13: [5,2,2,2,2]
14: [10,2,2]
15: [10,5]
16: [10,2,2,2]
17: [10,5,2]
18: [10,2,2,2,2]
19: [10,5,2,2]
20: [10,10]
21: [10,5,2,2,2]
22: [10,10,2]
23: [10,5,2,2,2,2]
24: [10,10,2,2]
25: [10,10,5]
26: [10,10,2,2,2]
27: [10,10,5,2]
28: [10,10,2,2,2,2]
29: [10,10,5,2,2]
30: [10,10,10]
31: [10,10,5,2,2,2]
32: [10,10,10,2]
33: [10,10,5,2,2,2,2]
34: [10,10,10,2,2]
35: [10,10,10,5]

Answer 4

This is a classic coin change problem.

---

Unfortunately, just applying a greedy approach(like you did) won't work since 1 ain't present in your denominations.

---

• To apply coin change algorithm here, we create an array called $amtPossible.

• This array will hold all the possible amounts we could make till $totalAmount(the total amount to be made).

• Every location of this array will hold 2 values. One is the minimum number of steps to get to this point and the other to tell us what was the last denomination that got us here.

• This will help us trace back what coins were actually involved in getting us the total amount ($totalAmount).

• The below code has $amtPossible[ $i ][0] > 1 + $amtPossible[ $i - $d ][0]. This simply means if the current denomination $d gives us less number of steps for a particular amount $i than what already exists for it, then update the $i with this new denomination. Rest is self-explanatory.

Snippet:

<?php

function getCoins(int $totalAmount, $denominations = [2 ,5, 10]){
    $amtPossible = [];
    foreach($denominations as $d){
        $amtPossible[ $d ]= [1, $d];
        for($i = $d + 1; $i <= $totalAmount; ++$i){
            if(isset($amtPossible[ $i - $d ])){
                if(!isset($amtPossible[ $i ]) || $amtPossible[ $i ][0] > 1 + $amtPossible[ $i - $d ][0]){
                    $amtPossible[ $i ][0] = 1 + $amtPossible[ $i - $d ][0];
                    $amtPossible[ $i ][1] = $d;
                }
            }
        }
    }
    
    if(!isset($amtPossible[ $totalAmount ])){
        throw new \Exception("$totalAmount is not possible with the denominations ". implode(",", $denominations));
    }
    
    $coins = [];
    while($totalAmount > 0){
        $coins[] = $amtPossible[ $totalAmount ][1];
        $totalAmount -= $amtPossible[ $totalAmount ][1];
    }
    
    return $coins;
}

print_r(getCoins(23));

Online Demo