loading...

Daily Challenge #262 - No One Likes Spare Change

thepracticaldev profile image dev.to staff ・1 min read

No one enjoys carrying around spare change. And to avoid all that jingling it's absolutely necessary to have an efficient algorithm to calculate the minimum number of coins needed to pay for something. So given a set of coin denominations determine the fewest number of coins required to add up to a given amount. Coin denominations WILL NOT be standard.

Example
US Currency includes the penny, nickel, dime and quarter or the coins with denominations: [1, 5, 10, 25] If I were to ask you to make 75 cents you would just return 3 since 75 cents can be made with 3 quarters.

Denominations:
coins1={1,5,10,25};
coins2={1,2,5,10,20,50};

Tests:
coins1(123)
coins2(123)
coins1(75)
coins2(75)

Good luck!


This challenge comes from RasPat1 on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Discussion

pic
Editor guide
Collapse
davidmmooney profile image
davidmmooney

That's not a good test suite. You want something that will break the naive implementation. Add

coins3={1,5,20,25}
coins3(40)

Collapse
sam_ferree profile image
Sam Ferree

This was always my favorite part of Topcoder.

Collapse
kvharish profile image
K.V.Harish

Not sure if this is an efficient solution but here is mine in JavaScript. I took the liberty to return an object instead of the number of coins and sorted the denominations instead of expecting it in order. I also added the test case suggested by davidmmooney.

const coins1 = [1, 5, 10, 25];
const coins2 = [1, 2, 5, 10, 20, 50];
const coins3 = [1, 5, 20, 25];
const coins4 = [2, 9, 5, 1];

const getChangeAsCoins = (coins, amount) => {
  coins = coins.sort((a, b) => a - b);
  let remaining = amount,
      index = coins.length - 1,
      change = {};

  while(remaining !== 0 || index !== -1) {
    numOfCoins = Math.floor(remaining / coins[index])
    change[coins[index]] = numOfCoins;
    remaining = remaining % coins[index];
    index--;
  }

  console.log(change);
}

getChangeAsCoins(coins1, 123);
/*
  {
    1: 3,
    5: 0,
    10: 2,
    25: 4
  }
*/
getChangeAsCoins(coins2, 123);
/*
  {
    1: 1,
    2: 1,
    5: 0,
    10: 0,
    20: 1,
    50: 2
  }
*/
getChangeAsCoins(coins1, 75);
/*
  {
    1: 0,
    5: 0,
    10: 0,
    25: 3
  }
*/
getChangeAsCoins(coins2, 75);
/*
  {
    1: 0,
    2: 0,
    5: 1,
    10: 0,
    20: 1,
    50: 1
  }
*/
getChangeAsCoins(coins3, 40);
/*
  {
    1: 0,
    5: 3,
    20: 0,
    25: 1
  }
*/
getChangeAsCoins(coins4, 53);
/*
  {
    1: 1,
    2: 1,
    5: 1,
    9: 5
  }
*/
Collapse
tinstaafl profile image
tinstaafl

the 'coins3,40' test returns the wrong answer it should be "20: 2"

Collapse
dry profile image
Hayden Mankin

I have to admit I fell for the naive solution until I read davidmmooneys comment. The problem is to find the least amount of coins, not to use as many of the largest denomination coin as possible.

My initial solution was as follows:

function GreedyCoinCounterFactory(denominations){
  denominations.sort((x, y) => y-x);
  return (amount) => {
    return denominations.reduce((acc, curr) => {
      acc += Math.floor(amount / curr);
      amount %= curr;
      return acc;
    }, 0);
  }
}

let coins1 = GreedyCoinCounterFactory([1,5,10,25]);
let coins2 = GreedyCoinCounterFactory([1,2,5,10,20,50]);
let coins3 = GreedyCoinCounterFactory([1,5,20,25]);

console.log(coins1(123)); // 9
console.log(coins2(123)); // 5
console.log(coins1(75));  // 3
console.log(coins2(75));  // 3
console.log(coins3(40));  // 4

Notice how the last test outputs 4. using this approach we find 25 + 5 + 5 + 5 = 40, although this is true, 20 + 20 = 40 is a better solution as it uses 2 coins.

The following is an improved solution based on the fact that you can divide the problem into sub problems that are also valid. for example if 20 + 20 + 1 + 1 = 42 is the best solution for 42 then 20 + 20 = 40 and 1 + 1 = 2 must be the best solution for 40 and 2 respectively. I start with the fact that you need 0 coins to get an amount of 0, then calculate the best amount for each amount between 0 and the input.

function DynamicCoinCounterFactory(denominations) {
  return (amount) => {
    let counts = [];
    counts.push(0);

    for(let i = counts.length; i <= amount; i++) {
      let min = amount;
      for(let j = 0; j < denominations.length; j++) {
        if (i >= denominations[j]) {
          min = Math.min(min, counts[i-denominations[j]]+1)
        }
      }
      counts.push(min);
    }
    return counts[counts.length-1];
  }
}

let coins1 = DynamicCoinCounterFactory([1,5,10,25]);
let coins2 = DynamicCoinCounterFactory([1,2,5,10,20,50]);
let coins3 = DynamicCoinCounterFactory([1,5,20,25]);

console.log(coins1(123)); // 9
console.log(coins2(123)); // 5
console.log(coins1(75));  // 3
console.log(coins2(75));  // 3
console.log(coins3(40));  // 2
Collapse
aminnairi profile image
Amin

Haskell

import Data.List (sort)


minimumChange :: [Int] -> Int -> Int
minimumChange coins amount =
    minimumChange' (reverse $ sort coins) amount

    where
        minimumChange' :: [Int] -> Int -> Int
        minimumChange' [] _                  = 0
        minimumChange' _ 0                   = 0
        minimumChange' (coin : coins) amount =
            (div amount coin)
                + minimumChange' coins (mod amount coin)
Collapse
agtoever profile image
agtoever

Wow. I really liked this one. I ended up writing a lot of lines, but well documented. What I really wanted to showcase here is that sometimes, creating a more general function really pays off. In this case, I created a function that returns a list of all possible coin configurations (sorted by number of coins). Once I had that, I just needed to return the first solution and add the number of coins.

Try it online!

from typing import List, Dict
import numpy


def split_in_denominations(amount: int,
                           denominations: List[int]) -> List[Dict[int, int]]:
    """ Gives all distinct ways to express amount in items from denominations

    The algorithm used is to find all solutions for each smaller amount and
    each smaller list of (sorted) denominations. For example, for the amount
    of 3 and denominations [1, 2], the following Numpy array is created:

             Amount:  |     0     |     1     |     2     |     3     |
    Denominations:    +-----------+-----------+-----------+-----------+
                  [1] |[{1:0,2:0}]|[{1:1,2:0}]|[{1:2,2:0}]|[{1:3,2:0}]|
                [1,2] |[{1:0,2:0}]|[{1:1,2:0}]|[{1:2,2:0},|[{1:3,2:0},|
                      |           |           | {1:0,2:1}]| {1:1,2:1}]|
                      +-----------+-----------+-----------+-----------+

    This result array is built row by row from the top left to the bottom
    right. For each cell, only two (disjunct!) solution sets have to be
    considered: the one directly above (not using the current denomination)
    and the one 1 of the denomination value to the left. For that latter set,
    you just need to count one extra of denomination.

    Arguments:
        amount: integer value that has to be expressed in denominations
        denominations: list of values

    Returns:
        List with all unique dicts with denomination as key and the count
        of that denomination as value. The list is sorted by the sum of
        the count of all denominations (the least number of coins)

    Raises:
        ValueError is the amount can't be expressed by denominations

    Examples:
        >>> split_in_denominations(13, [1, 5, 10, 25])
        [{1: 3, 5: 0, 10: 1, 25: 0},   # 3 coins
         {1: 3, 5: 2, 10: 0, 25: 0},   # 5 coins
         {1: 8, 5: 1, 10: 0, 25: 0},   # 9 coins
         {1: 13, 5: 0, 10: 0, 25: 0}]  # 13 coins
    """

    # Template solution: an empty dict with count 0 of each denominations
    zero_denom = {d: 0 for d in denominations}

    # Edge case: amount == 0
    if amount == 0:
        return [zero_denom]

    # result array with all intermediate solutions
    result = numpy.ndarray((amount + 1, len(denominations)), dtype=list)

    # Loop over the sorted denominations
    for denom_idx, denom in enumerate(sorted(denominations)):
        for amount_idx in range(amount + 1):
            # In the first iteration of denom, fill the first row of result
            if denom_idx == 0:
                # Start with a copy of the template solution
                result[amount_idx, 0] = [dict(zero_denom)]

                # If amount is divisible by denom, add that solution
                if amount_idx % denom == 0:
                    result[amount_idx, 0][0][denom] = amount_idx // denom

            # Now add the other denominations one by one in each loop
            else:
                # Copy the results from the previous denomination list
                result[amount_idx, denom_idx] = list(result[amount_idx,
                                                            denom_idx - 1])

                # Extend the result with the solutions from
                # amount_idx minus denom, with 1 extra count of denom
                if amount_idx >= denom:
                    for solution in result[amount_idx - denom, denom_idx]:
                        new_solution = dict(solution)
                        new_solution[denom] += 1
                        result[amount_idx, denom_idx].append(new_solution)

    # Check if there is a result (result does not only contain the template)
    if result[amount, len(denominations) - 1] == [zero_denom]:
        raise ValueError(f"{amount} can't be expressed in {denominations}")

    return sorted(result[amount, len(denominations) - 1],
                  key=lambda s: sum(s.values()))


def least_num_denominations(amount: float,
                            denominations: List[float]) -> int:
    """ Gives the least number of denominations that is needed to sum to amount

    Arguments:
        amount: numeric value that has to be expressed in denominations
        denominations: list of values

    Returns:
        The least number of denominations.
        Returns None of there is no possible split into denominations.

    Examples:
        >>> least_num_denominations(4, [1, 2, 3])  # (2, 2) or (1, 3)
        2
    """
    return sum(split_in_denominations(amount, denominations)[0].values())


def main():
    denominations = {'coins1': [1, 5, 10, 25],
                     'coins2': [1, 2, 5, 10, 20, 50],
                     'coins3': [1, 5, 20, 25],
                     }

    cases = [('coins1', 13),  # 123),
             ('coins2', 13),  # 123),
             ('coins1', 75),
             ('coins2', 75),
             ('coins3', 40),
             ]

    for den_name, amount in cases:
        d = denominations[den_name]
        print(f'Least split of {amount} in {d} is: ' +
              f'{least_num_denominations(amount, d)} (there are ' +
              f'{len(split_in_denominations(amount, d))} ways to split)')


if __name__ == '__main__':
    main()
Collapse
jurerotar profile image
Jure Rotar

Since we're looking for the least amount of coins, we sort the array and start looping from the biggest coin value. We check if total amount is higher than our current coin value and if it is, add the coin to the 'purse' and substract the value of the coin from the total amount.

function getChangeAsCoins(array $coins, int $amount): array {
    $numberOfCoins = count($coins);
    sort($coins);
    $returnedCoins = [];
    for($i = $numberOfCoins - 1; $i >= 0; $i -- ) {
        while($amount >= $coins[$i]) {
            $amount -= $coins[$i];
            $returnedCoins[] = $coins[$i];
        }
    }
    return $returnedCoins;
}