# Exact change in fewest bills and coins [duplicate]

## 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 • I thought this was a dupe, but I can't find it. The closest ones are this and this, and this, and this.... Jun 15, 2017 at 23:22 • Actually, I think it is a dupe of the third one. That challenge is very old, however, so it may not be worth closing this one... I'll let other users decide because my dupe vote is binding. Jun 15, 2017 at 23:32 • No 20 dollar bill? – xnor Jun 15, 2017 at 23:36 • @xnor Forgot that, fixed. Thanks. Jun 15, 2017 at 23:37 • Looks like it's a dupe down to the fact that it has a bonus with unclear effects on the win and validity conditions, together with a win condition that's just implied by the tag rather than stated in the question. I'd be willing to vote to close this due to the inclarity in the win condition, in addition to the fact that it's a duplicate. – user62131 Jun 16, 2017 at 0:35 ## 5 Answers # 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 + • Should have known Mathematica would have a built-in for this. Awesome. Jun 15, 2017 at 23:22 • What changed to make you need to add 2 bytes? Jun 15, 2017 at 23:27 • wrong count. this is the correct number Jun 15, 2017 at 23:29 # 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! # 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.

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

• Welcome to PPCG! In the JS answer you can leave off the leading 0s in the decimal numbers. Also, it would be best to post these as two separate answers (though that is no longer possible due to the question being closed). Jun 16, 2017 at 1:55
• user75200 suggested the following improvement in an edit (which I rejected): f=m=>{for(i of(d=[100,50,20,10,5,2,1,.25,.1,.05,.01]))alert((m-=(z=Math.round(m/i)*i),z))} Feel free to review and use it if it's correct. Oct 24, 2017 at 12:38

# Python 2, 539490 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

• My understanding is that the code must work for US currencies without taking it as an extra input. Also, this greedy strategy doesn't work with general currencies, like [5,4,1] on input 8.
– xnor
Jun 15, 2017 at 23:59
• Shouldn't the denominations be part of the function rather than the input? Jun 15, 2017 at 23:59
• @xnor I think you commented before my edit, I had accidentally submitted before finishing. Jun 16, 2017 at 0:02
• Edited to work with US currency without extra input. Jun 16, 2017 at 0:08