Sha256: 78c61987a10b79bdfff61ae590ac46637750463850c5cb37b9085cb8f0306c03

Contents?: true

Size: 1.63 KB

Versions: 396

Compression:

Stored size: 1.63 KB

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.159 tracks/php/exercises/change/example.php
trackler-2.2.1.158 tracks/php/exercises/change/example.php
trackler-2.2.1.157 tracks/php/exercises/change/example.php
trackler-2.2.1.156 tracks/php/exercises/change/example.php
trackler-2.2.1.155 tracks/php/exercises/change/example.php
trackler-2.2.1.154 tracks/php/exercises/change/example.php
trackler-2.2.1.153 tracks/php/exercises/change/example.php
trackler-2.2.1.152 tracks/php/exercises/change/example.php
trackler-2.2.1.151 tracks/php/exercises/change/example.php
trackler-2.2.1.150 tracks/php/exercises/change/example.php
trackler-2.2.1.149 tracks/php/exercises/change/example.php
trackler-2.2.1.148 tracks/php/exercises/change/example.php
trackler-2.2.1.147 tracks/php/exercises/change/example.php
trackler-2.2.1.146 tracks/php/exercises/change/example.php
trackler-2.2.1.145 tracks/php/exercises/change/example.php
trackler-2.2.1.144 tracks/php/exercises/change/example.php
trackler-2.2.1.143 tracks/php/exercises/change/example.php
trackler-2.2.1.142 tracks/php/exercises/change/example.php
trackler-2.2.1.141 tracks/php/exercises/change/example.php
trackler-2.2.1.140 tracks/php/exercises/change/example.php