# Daily Challenge #262 - No One Likes Spare Change

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  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
}
*/
`````` 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
`````` Amin

``````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)
`````` 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.

``````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: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:
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][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).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()
`````` 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;
}
``````  