Find minimum number of coins that make a given value
- Task
Find and show here on this page the minimum number of coins that can make a value of 988.
Available coins are: 1, 2, 5, 10, 20, 50, 100, and 200.
The coins that would be dispensed are:
four coins of 200
one coin of 100
one coin of 50
one coin of 20
one coin of 10
one coin of 5
one coin of 2
one coin of 1
AppleScript
<lang applescript>----------------- MINIMUM NUMBER OF COINS ----------------
-- change :: [Int] -> Int -> [(Int, Int)] on change(units, n)
if {} = units or 0 = n then
{}
else
set {x, xs} to {item 1 of units, rest of units}
set q to n div x
if 0 = q then
change(xs, n)
else
Template:Q, x & change(xs, n mod x)
end if
end if
end change
TEST -------------------------
on run
set coinReport to ¬
showChange({200, 100, 50, 20, 10, 5, 2, 1})
unlines(map(coinReport, {1024, 988}))
end run
-- showChange :: [Int] -> Int -> String
on showChange(units)
script
on |λ|(n)
script go
on |λ|(qd)
set {q, d} to qd
(q as text) & " * " & d as text
end |λ|
end script
unlines({("Summing to " & n as text) & ":"} & ¬
map(go, change(units, n))) & linefeed
end |λ|
end script
end showChange
GENERIC ------------------------
-- map :: (a -> b) -> [a] -> [b] on map(f, xs)
-- The list obtained by applying f
-- to each element of xs.
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
-- 2nd class handler function lifted into 1st class script wrapper.
if script is class of f then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- unlines :: [String] -> String
on unlines(xs)
-- A single string formed by the intercalation
-- of a list of strings with the newline character.
set {dlm, my text item delimiters} to ¬
{my text item delimiters, linefeed}
set s to xs as text
set my text item delimiters to dlm
s
end unlines</lang>
- Output:
Summing to 1024: 5 * 200 1 * 20 2 * 2 Summing to 988: 4 * 200 1 * 100 1 * 50 1 * 20 1 * 10 1 * 5 1 * 2 1 * 1
F#
<lang fsharp> //Find minimum number of coins that make a given value - Nigel Galloway: August 12th., 20 let fN g=let rec fG n g=function h::t->fG((g/h,h)::n)(g%h) t |_->n in fG [] g [200;100;50;20;10;5;2;1] fN 988|>List.iter(fun(n,g)->printfn "Take %d of %d" n g) </lang>
- Output:
Take 1 of 1 Take 1 of 2 Take 1 of 5 Take 1 of 10 Take 1 of 20 Take 1 of 50 Take 1 of 100 Take 4 of 200
Factor
<lang factor>USING: assocs kernel math math.order prettyprint sorting ;
- make-change ( value coins -- assoc )
[ >=< ] sort [ /mod swap ] zip-with nip ;
988 { 1 2 5 10 20 50 100 200 } make-change .</lang>
- Output:
{
{ 200 4 }
{ 100 1 }
{ 50 1 }
{ 20 1 }
{ 10 1 }
{ 5 1 }
{ 2 1 }
{ 1 1 }
}
Go
<lang go>package main
import "fmt"
func main() {
denoms := []int{200, 100, 50, 20, 10, 5, 2, 1}
coins := 0
amount := 988
remaining := 988
fmt.Println("The minimum number of coins needed to make a value of", amount, "is as follows:")
for _, denom := range denoms {
n := remaining / denom
if n > 0 {
coins += n
fmt.Printf(" %3d x %d\n", denom, n)
remaining %= denom
if remaining == 0 {
break
}
}
}
fmt.Println("\nA total of", coins, "coins in all.")
}</lang>
- Output:
The minimum number of coins needed to make a value of 988 is as follows:
200 x 4
100 x 1
50 x 1
20 x 1
10 x 1
5 x 1
2 x 1
1 x 1
A total of 11 coins in all.
Haskell
<lang haskell>import Data.List (mapAccumL) import Data.Tuple (swap)
FIND CHANGE ----------------------
change :: [Int] -> Int -> [(Int, Int)] change xs n = zip (snd $ mapAccumL go n xs) xs
where go m v = swap (quotRem m v)
TEST -------------------------
main :: IO () main =
mapM_ print $ change [200, 100, 50, 20, 10, 5, 2, 1] 988</lang>
- Output:
(4,200) (1,100) (1,50) (1,20) (1,10) (1,5) (1,2) (1,1)
Or as a hand-written recursion, defining a slightly more parsimonious listing, and allowing for denomination lists which are ill-sorted or incomplete.
<lang haskell>import Data.List (sortOn) import Data.Ord (Down (Down))
MINIMUM NUMBER OF COINS TO MAKE A SUM ---------
change :: [Int] -> Int -> Either String [(Int, Int)] change units n
| 0 == mod n m = Right $ go (sortOn Down units) (abs n)
| otherwise =
Left $
concat
[ "Residue of ",
show (mod n m),
" - no denomination smaller than ",
show m,
"."
]
where
m = minimum units
go _ 0 = []
go [] _ = []
go (x : xs) n
| 0 == q = go xs n
| otherwise = (q, x) : go xs r
where
(q, r) = quotRem n x
TEST -------------------------
main :: IO () main = mapM_ putStrLn $ test <$> [1024, 988]
where
test n =
either
id
( concat
. (:) ("Summing to " <> show n <> ":\n")
. fmap
( \(q, v) ->
concat
[show q, " * ", show v, "\n"]
)
)
(change [200, 100, 50, 20, 10, 5, 2, 1] n)</lang>
- Output:
Summing to 1024: 5 * 200 1 * 20 2 * 2 Summing to 988: 4 * 200 1 * 100 1 * 50 1 * 20 1 * 10 1 * 5 1 * 2 1 * 1
jq
Works with gojq, the Go implementation of jq <lang jq>
- If $details then provide {details, coins}, otherwise just the number of coins.
def minimum_number($details):
. as $amount
| [200, 100, 50, 20, 10, 5, 2, 1] as $denoms
| {coins: 0, remaining: 988, details: []}
| label $out
| foreach $denoms[] as $denom (.;
((.remaining / $denom)|floor) as $n
| if $n > 0
then .coins += $n
| if $details then .details += [{$denom, $n}] else . end
| .remaining %= $denom
else . end;
if .remaining == 0 then ., break $out else empty end)
| if $details then {details, coins} else .coins end ;
- Verbose mode:
def task:
"\nThe minimum number of coins needed to make a value of \(.) is as follows:",
(minimum_number(true)
| .details[],
"\nA total of \(.coins) coins in all." );
988
| minimum_number(false), # illustrate minimal output
task # illustrate detailed output
</lang>
- Output:
11
The minimum number of coins needed to make a value of 988 is as follows:
{"denom":200,"n":4}
{"denom":100,"n":1}
{"denom":50,"n":1}
{"denom":20,"n":1}
{"denom":10,"n":1}
{"denom":5,"n":1}
{"denom":2,"n":1}
{"denom":1,"n":1}
A total of 11 coins in all.
Julia
Long version
Using a linear optimizer for this is serious overkill, but why not? <lang julia>using JuMP, GLPK
model = Model(GLPK.Optimizer) @variable(model, ones, Int) @variable(model, twos, Int) @variable(model, fives, Int) @variable(model, tens, Int) @variable(model, twenties, Int) @variable(model, fifties, Int) @variable(model, onehundreds, Int) @variable(model, twohundreds, Int) @constraint(model, ones >= 0) @constraint(model, twos >= 0) @constraint(model, fives >= 0) @constraint(model, tens >= 0) @constraint(model, twenties >= 0) @constraint(model, fifties >= 0) @constraint(model, onehundreds >= 0) @constraint(model, twohundreds >= 0) @constraint(model, 988 == 1ones +2twos + 5fives + 10tens + 20twenties + 50fifties + 100onehundreds + 200twohundreds)
@objective(model, Min, ones + twos + fives + tens + twenties + fifties + onehundreds + twohundreds)
optimize!(model) println("Optimized total coins: ", objective_value(model)) for val in [ones, twos, fives, tens, twenties, fifties, onehundreds, twohundreds]
println("Value of ", string(val), " is ", value(val))
end
</lang>
- Output:
Optimized total coins: 11.0 Value of ones is 1.0 Value of twos is 1.0 Value of fives is 1.0 Value of tens is 1.0 Value of twenties is 1.0 Value of fifties is 1.0 Value of onehundreds is 1.0 Value of twohundreds is 4.0
Brief REPL command version
julia> accumulate((x, y) -> (x[1] % y, (y, x[1] ÷ y)), [200, 100, 50, 20, 10, 5, 2, 1], init=(988, 0))
8-element Vector{Tuple{Int64, Tuple{Int64, Int64}}}:
(188, (200, 4))
(88, (100, 1))
(38, (50, 1))
(18, (20, 1))
(8, (10, 1))
(3, (5, 1))
(1, (2, 1))
(0, (1, 1))
MiniZinc
<lang MiniZinc> %Find minimum number of coins that make a given value. Nigel Galloway, August 11th., 2021 int: N=988; array [1..8] of int: coinValue=[1,2,5,10,20,50,100,200]; array [1..8] of var 0..N: take; constraint sum(n in 1..8)(take[n]*coinValue[n])=N; solve minimize sum(n in 1..8)(take[n]); output(["Take "++show(take[n])++" of "++show(coinValue[n])++"\n" | n in 1..8]) </lang>
- Output:
Take 1 of 1 Take 1 of 2 Take 1 of 5 Take 1 of 10 Take 1 of 20 Take 1 of 50 Take 1 of 100 Take 4 of 200 ---------- ========== Finished in 196msec
Nim
<lang Nim>import strformat
const
Coins = [200, 100, 50, 20, 10, 5, 2, 1] Target = 988
echo &"Minimal number of coins to make a value of {Target}:" var count = 0 var remaining = Target for coin in Coins:
let n = remaining div coin
if n != 0:
inc count, n
echo &"coins of {coin:3}: {n}"
dec remaining, n * coin
if remaining == 0: break
echo "\nTotal: ", count</lang>
- Output:
Minimal number of coins to make a value of 988: coins of 200: 4 coins of 100: 1 coins of 50: 1 coins of 20: 1 coins of 10: 1 coins of 5: 1 coins of 2: 1 coins of 1: 1 Total: 11
Phix
with javascript_semantics requires("1.0.1") -- (lastdelim added to the join() function) sequence coins = {1,2,5,10,20,50,100,200} string strc = join(apply(coins,sprint),", ", ", and ") atom total = 988 printf(1,"Make a value of %d using the coins %s:\n",{total,strc}) integer count = 0 for i=length(coins) to 1 by -1 do integer ci = coins[i], c = floor(total/ci) if c then printf(1,"%6s coin%s of %3d\n",{ordinal(c,true),iff(c>1?"s":" "),ci}) count += c total = remainder(total,ci) if total=0 then exit end if end if end for printf(1,"%s coins were used.\n",{proper(ordinal(count,true))})
- Output:
Make a value of 988 using the coins 1, 2, 5, 10, 20, 50, 100, and 200: four coins of 200 one coin of 100 one coin of 50 one coin of 20 one coin of 10 one coin of 5 one coin of 2 one coin of 1 Eleven coins were used.
Python
Python :: Procedural
<lang python>def makechange(denominations = [1,2,5,10,20,50,100,200], total = 988):
print(f"Available denominations: {denominations}. Total is to be: {total}.")
coins, remaining = sorted(denominations, reverse=True), total
for n in range(len(coins)):
coinsused, remaining = divmod(remaining, coins[n])
if coinsused > 0:
print(" ", coinsused, "*", coins[n])
makechange()
</lang>
- Output:
Available denominations: [1, 2, 5, 10, 20, 50, 100, 200]. Total is to be: 988.
4 * 200
1 * 100
1 * 50
1 * 20
1 * 10
1 * 5
1 * 2
1 * 1
Python :: Functional
<lang python>Minimum number of coins to make a given value
- change :: [Int] -> Int -> [(Int, Int)]
def change(xs):
A list of (quantity, denomination) pairs.
Unused denominations are excluded from the list.
def go(n):
if xs and n:
h, *t = xs
q, r = divmod(n, h)
return ([(q, h)] if q else []) + (
change(t)(r)
)
else:
return []
return go
- ------------------------- TEST -------------------------
- main :: IO ()
def main():
Testing a set of denominations with two sums
f = change([200, 100, 50, 20, 10, 5, 2, 1])
print(
"\n".join([
f'Summing to {n}:\n' + "\n".join([
f'{qu[0]} * {qu[1]}' for qu in f(n)]
) + "\n"
for n in [1024, 988]
])
)
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
Summing to 1024: 5 * 200 1 * 20 2 * 2 Summing to 988: 4 * 200 1 * 100 1 * 50 1 * 20 1 * 10 1 * 5 1 * 2 1 * 1
Raku
Since unit denominations are possible, don't bother to check to see if an exact pay-out isn't possible.
<lang perl6>my @denominations = 200, 100, 50, 20, 10, 5, 2, 1;
sub change (Int $n is copy where * >= 0) { gather for @denominations { take $n div $_; $n %= $_ } }
for 988, 1307, 37511, 0 -> $amount {
say "\n$amount:"; printf "%d × %d\n", |$_ for $amount.&change Z @denominations;
}</lang>
- Output:
988: 4 × 200 1 × 100 1 × 50 1 × 20 1 × 10 1 × 5 1 × 2 1 × 1 1307: 6 × 200 1 × 100 0 × 50 0 × 20 0 × 10 1 × 5 1 × 2 0 × 1 37511: 187 × 200 1 × 100 0 × 50 0 × 20 1 × 10 0 × 5 0 × 2 1 × 1 0: 0 × 200 0 × 100 0 × 50 0 × 20 0 × 10 0 × 5 0 × 2 0 × 1
REXX
A check was made to see if an exact pay─out isn't possible.
The total number of coins paid out is also shown. <lang rexx>/*REXX pgm finds & displays the minimum number of coins which total to a specified value*/ parse arg $ coins /*obtain optional arguments from the CL*/ if $= | $="," then $= 988 /*Not specified? Then use the default.*/ if coins= | coins="," then coins= 1 2 5 10 20 50 100 200 /* ... " " " " */
- = words(coins) /*#: is the number of allowable coins.*/
w= 0 /*width of largest coin (for alignment)*/
do j=1 for #; @.j= word(coins, j) /*assign all coins to an array (@.). */
w= max(w, length(@.j) ) /*find the width of the largest coin. */
end /*j*/
say 'available coin denominations: ' coins /*shown list of available denominations*/ say say center(' making change for ' $, 30 ) /*display title for the upcoming output*/ say center( , 30, "─") /* " sep " " " " */ koins= 0 /*the total number of coins dispensed. */ paid= 0 /*the total amount of money paid so far*/
do k=# by -1 for #; z= $ % @.k /*start with largest coin for payout. */
if z<1 then iterate /*if Z is not positive, then skip coin.*/
koins= koins + z
paid= z * @.k /*pay out a number of coins. */
$= $ - paid /*subtract the pay─out from the $ total*/
say right(z,9) ' of coin ' right(@.k, w) /*display how many coins were paid out.*/
end /*k*/
say center( , 30, "─") /* " sep " " " " */ say say 'number of coins dispensed: ' koins if $>0 then say 'exact payout not possible.' /*There a residue? Payout not possible*/ exit 0 /*stick a fork in it, we're all done. */</lang>
- output when using the default inputs:
available coin denominations: 1 2 5 10 20 50 100 200
making change for 988
──────────────────────────────
4 of coin 200
1 of coin 100
1 of coin 50
1 of coin 20
1 of coin 10
1 of coin 5
1 of coin 2
1 of coin 1
──────────────────────────────
number of coins dispensed: 11
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl see "Coins are:" + nl sum = 988
sumCoins = 0 coins = [1,2,5,10,20,50,100,200] coins = reverse(coins)
for n = 1 to len(coins)
nr = floor(sum/coins[n])
if nr > 0
sumCoins= nr*coins[n]
sum -= sumCoins
see "" + nr + "*" + coins[n] + nl
ok
next
see "done..." + nl </lang>
- Output:
working... Coins are: 4*200 1*100 1*50 1*20 1*10 1*5 1*2 1*1 done...
Rust
<lang rust> fn main() {
let denoms = vec![200, 100, 50, 20, 10, 5, 2, 1];
let mut coins = 0;
let amount = 988;
let mut remaining = 988;
println!("The minimum number of coins needed to make a value of {} is as follows:", amount);
for denom in denoms.iter() {
let n = remaining / denom;
if n > 0 {
coins += n;
println!(" {} x {}", denom, n);
remaining %= denom;
if remaining == 0 {
break;
}
}
}
println!("\nA total of {} coins in all.", coins);
} </lang>
- Output:
The minimum number of coins needed to make a value of 988 is as follows: 200 x 4 100 x 1 50 x 1 20 x 1 10 x 1 5 x 1 2 x 1 1 x 1 A total of 11 coins in all.
Wren
As there is, apparently, an unlimited supply of coins of each denomination, it follows that any amount can be made up. <lang ecmascript>import "/fmt" for Fmt
var denoms = [200, 100, 50, 20, 10, 5, 2, 1] var coins = 0 var amount = 988 var remaining = 988 System.print("The minimum number of coins needed to make a value of %(amount) is as follows:") for (denom in denoms) {
var n = (remaining / denom).floor
if (n > 0) {
coins = coins + n
Fmt.print(" $3d x $d", denom, n)
remaining = remaining % denom
if (remaining == 0) break
}
} System.print("\nA total of %(coins) coins in all.")</lang>
- Output:
The minimum number of coins needed to make a value of 988 is as follows:
200 x 4
100 x 1
50 x 1
20 x 1
10 x 1
5 x 1
2 x 1
1 x 1
A total of 11 coins in all.
XPL0
<lang XPL0>int Denom, Denoms, Coins, Amount, Remaining, I, N; [Denoms:= [200, 100, 50, 20, 10, 5, 2, 1]; Coins:= 0; Amount:= 988; Remaining:= 988; Text(0, "The minimum number of coins needed to make a value of "); IntOut(0, Amount); Text(0, " is as follows: "); Format(3, 0); for I:= 0 to 7 do
[Denom:= Denoms(I);
N:= Remaining/Denom;
if N > 0 then
[Coins:= Coins + N;
RlOut(0, float(Denom)); Text(0, " x "); IntOut(0, N); CrLf(0);
Remaining:= rem(Remaining/Denom);
if Remaining = 0 then I:= 7;
];
];
Text(0, " A total of "); IntOut(0, Coins); Text(0, " coins in all. "); ]</lang>
- Output:
The minimum number of coins needed to make a value of 988 is as follows: 200 x 4 100 x 1 50 x 1 20 x 1 10 x 1 5 x 1 2 x 1 1 x 1 A total of 11 coins in all.