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.119	tracks/php/exercises/change/example.php
trackler-2.2.1.118	tracks/php/exercises/change/example.php
trackler-2.2.1.117	tracks/php/exercises/change/example.php
trackler-2.2.1.116	tracks/php/exercises/change/example.php
trackler-2.2.1.115	tracks/php/exercises/change/example.php
trackler-2.2.1.114	tracks/php/exercises/change/example.php
trackler-2.2.1.113	tracks/php/exercises/change/example.php
trackler-2.2.1.111	tracks/php/exercises/change/example.php
trackler-2.2.1.110	tracks/php/exercises/change/example.php
trackler-2.2.1.109	tracks/php/exercises/change/example.php
trackler-2.2.1.108	tracks/php/exercises/change/example.php
trackler-2.2.1.107	tracks/php/exercises/change/example.php
trackler-2.2.1.106	tracks/php/exercises/change/example.php
trackler-2.2.1.105	tracks/php/exercises/change/example.php
trackler-2.2.1.104	tracks/php/exercises/change/example.php
trackler-2.2.1.103	tracks/php/exercises/change/example.php
trackler-2.2.1.102	tracks/php/exercises/change/example.php
trackler-2.2.1.101	tracks/php/exercises/change/example.php
trackler-2.2.1.100	tracks/php/exercises/change/example.php
trackler-2.2.1.99	tracks/php/exercises/change/example.php