# What is the smallest number of coins that make this total?

I was reading thishttp://forums.theregister.co.uk/forum/1/2011/… (a horrible piece of writing, where the grammar was so bad I was often left wondering what the writer intended) and in the comments someone asked:

“given x denominations, what’s the smallest number of coins required to make y”

and I felt like answering it:

```
# encoding: UTF-8
# "given x denominations, what's the smallest number of coins required to make y"
Target = ARGV[0].nil? ? rand(1000) : ARGV[0].to_i
Denominations = [100, 50, 20, 10, 5, 2, 1]
def coins_required( total, denom=0 )
res, rem = total.divmod Denominations[denom]
res += coins_required( rem, denom + 1 ) unless rem.zero?
res
end
puts "The target is #{Target}"
puts "Smallest number of coins required is: #{coins_required Target}"
```

Here’s a quick spec for the code above:

```
require 'rspec'
describe :coins_required do
context "Given a total of 0" do
subject {coins_required 0}
it { should == 0 }
end
context "Given a total of 1" do
subject {coins_required 1}
it { should == 1 }
end
context "Given a total of 319" do
subject {coins_required 319}
it { should == 7 }
end
end
```