Contents

<?php

function findFewestCoins($coins, $targetValue)
{
    if ($targetValue == 0) {
        return array(); // no coins
    }
    if ($targetValue < 0) {
        throw new InvalidArgumentException('Cannot make change for negative value');
    }
    if (min($coins) > $targetValue) {
        throw new InvalidArgumentException('No coins small enough to make change');
    }

    $minCoins = [];

    // populate the minCoins array with the minimum number of coins
    // needed to make each step, from 0 up to our target value
    foreach (range(0, $targetValue) as $step) {
        // if the step is one of our coins, then just use that coin
        if (in_array($step, $coins)) {
            $minCoins[$step] = array($step);
        } else {
            foreach ($coins as $coin) {
                // ignore if the coin value is bigger than our step.
                if ($coin > $step) {
                    continue;
                }

                // lookup the minimum number of coins to make the step, minus the value of the current coin
                $lastCoins = $minCoins[$step - $coin];

                // if there is no minCoins currently set for this step, or if the number of coins
                // is greater than the number of coins it takes to make the last step, plus one new coin...
                if (!isset($minCoins[$step]) || count($minCoins[$step]) > 1 + count($lastCoins)) {
                    // set to the current coin, with the coins needed to make the last step
                    $minCoins[$step] = array_merge(array($coin), $lastCoins);
                }
            }
        }
    }

    return $minCoins[$targetValue];
}

Version data entries

396 entries across 396 versions & 1 rubygems

Version	Path
trackler-2.2.1.180	tracks/php/exercises/change/example.php
trackler-2.2.1.179	tracks/php/exercises/change/example.php
trackler-2.2.1.178	tracks/php/exercises/change/example.php
trackler-2.2.1.177	tracks/php/exercises/change/example.php
trackler-2.2.1.176	tracks/php/exercises/change/example.php
trackler-2.2.1.175	tracks/php/exercises/change/example.php
trackler-2.2.1.174	tracks/php/exercises/change/example.php
trackler-2.2.1.173	tracks/php/exercises/change/example.php
trackler-2.2.1.172	tracks/php/exercises/change/example.php
trackler-2.2.1.171	tracks/php/exercises/change/example.php
trackler-2.2.1.170	tracks/php/exercises/change/example.php
trackler-2.2.1.169	tracks/php/exercises/change/example.php
trackler-2.2.1.167	tracks/php/exercises/change/example.php
trackler-2.2.1.166	tracks/php/exercises/change/example.php
trackler-2.2.1.165	tracks/php/exercises/change/example.php
trackler-2.2.1.164	tracks/php/exercises/change/example.php
trackler-2.2.1.163	tracks/php/exercises/change/example.php
trackler-2.2.1.162	tracks/php/exercises/change/example.php
trackler-2.2.1.161	tracks/php/exercises/change/example.php
trackler-2.2.1.160	tracks/php/exercises/change/example.php