Exact change in fewest bills and coins [duplicate]

Question

Overview

In the US, the common denominations are the penny ($0.01), the nickel ($0.05), the dime ($0.10), the quarter ($0.25), one dollar, two dollars (less common but lets pretend it's common), five dollars, ten dollars, twenty dollars, fifty dollars, and one hundred dollars. ($1 to $100 respectively).

Your goal is to take an arbitrary money value and output a list of the fewest bills and coins that add up to that amount.

Rules

• The output must be minimal. You cannot output "4175 pennies" for $41.75.
• The inputs and outputs can be any format or type, as long as you can explain what it means.
• Values must be kept the same. For instance, your program cannot accept "6523" for $65.23. It must accept the decimal value "65.23"

Examples

If the input is $185.24, the output should be something like
$100 + $50 + $20 + $10 + $5 + $0.10 + $0.10 + $0.01 + $0.01 + $0.01 + $0.01

For the input $44.75, another acceptable output would be
[0, 0, 2, 0, 0, 2, 0, 3, 0, 0, 0]
Meaning 2 $20s, 2 $2s, 3 quarters, and 0 of the other denominations.

Bonus

Accept another argument for the list of denominations so your program will work in other countries.

For example, if it's given this list of denominations.
[15, 7, 2.5, 1, 0.88, 0.2, 0.01]
and the money value "37.6", it should return something like
15 + 15 + 7 + 0.2 + 0.2 + 0.2

Answer 1

Mathematica, 54 bytes

#~NumberDecompose~{100,50,20,10,5,2,1,.25,.1,.05,.01}&

input

[44.75]

output

{0, 0, 2, 0, 0, 2, 0, 3, 0, 0, 0.}

Mathematica, 82 bytes --WITH BONUS--

(s=#~NumberDecompose~#2;Row@Flatten@Table[Table[#2[[i]]"+",s[[i]]],{i,Length@s}])&

Input

[37.6, {15, 7, 2.5, 1, 0.88, 0.2, 0.01}]

output

15 +15 +7 +0.2 +0.2 +0.2 +

Answer 2

PHP, 96 bytes

for(;$i<11;)$argn-=$c*$r[]=$argn/($c=[100,50,20,10,5,2,1,.25,.10,.05,.01][+$i++])^0;print_r($r);

Try it online!

Answer 3

Python 2, 73 bytes

x=input()+1e-5
for c in 100,50,20,10,5,2,1,.25,.1,.05,.01:print x//c;x%=c

Try it online!

A greedy strategy works for these values. Going through currencies largest to smallest, we remove the greatest whole number of the currency, leaving the modulo as the remainder. This repeated divmod is effectively mixed based conversion.

The +1e-5 is to ward off floating point errors where $0.09999999999999998 is left but that's less than 1 cent.

I thought about compressing the list of values but didn't think of a good approach. There's not a uniform pattern for the values.

Answer 4

Javascript(ES6), 97 bytes with bonus

f=(m,d=[100,50,20,10,5,2,1,0.25,0.1,0.05,0.01])=>{for(i of d){z=Math.round(m/i);alert(z);m-=z*i}}

Java, 209 bytes

so verbose...

interface A{static void main(String[]a){int m=Integer.valueOf(a[0]);for(double i:new Double[]{100.0,50.0,20.0,10.0,5.0,2.0,1.0,0.25,0.1,0.05,0.01}){int z = (int)Math.round(m/i);System.out.println(z);m-=z*i;}}}

Both use same algorithm as jacoblaw's.

Answer 5

Python 2, 53 94 90 78 bytes with bonus

def f(m,d=[100,50,20,10,5,2,1,.25,.1,.05,.01]):
 for i in d:
    print m//i
    m%=i

*The indentation is a space for line 2, and tabs for the other lines

The function takes in the amount of money and a sorted list of the denominations (if not US).

Examples:

>>> f(44.75)
0.0
0.0
2.0
0.0
0.0
2.0
0.0
3.0
0.0
0.0
0.0
>>> f(37.6, [15, 7, 2.5, 1, 0.88, 0.2, 0.01])
2.0
1.0
0.0
0.0
0.0
3.0
0.0
>>> f(8, [5,4,1])
1
0
3