Find minimum number of coins that make a given value

Find minimum number of coins that make a given value is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

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

Works with: Factor version 0.99 2021-06-02

<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

Translation of: Wren

<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 (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
       ( \qvs ->
           concat $
             "Summing to " <> show n <> ":\n" :
             fmap
               ( \(q, v) ->
                   concat [show q, " * ", show v, "\n"]
               )
               qvs
       )
       (change [200, 100, 50, 20, 10, 5] 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

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

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
sequence coins = {1,2,5,10,20,50,100,200}
atom total = 988
string sc = join(apply(coins,sprint),", ")
integer k = rfind(',',sc), count = 0
sc[k..k] = " and"
printf(1,"Make a value of %d using the coins %s:\n",{total,sc})
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

1. 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

1. ------------------------- TEST -------------------------
2. 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]
       ])
   )

1. 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 /* ... " " " " */

1. = 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...

Wren

Library: Wren-fmt

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.