A common computer science interview question goes something like this:

“Write a program that makes change with a minimum amount of coins for a given amount – a ‘Coin Maker’, if you will. You have unlimited amount of 1¢, 5¢, 10¢, and 25¢ coins. For example, \$2.16 would consist of 8 quarters, 1 dime, 1 nickle, and 1 penny: 11 total coins.”

Many would advise to solve this problem with Dynamic Programming (DP), but I personally find DP to be unnecessary in this scenario. Vanilla recursion is a better solution.

To solve for the number of coins only:

def choose_next_coin(remaining_amount, coins_dispensed)
return coins_dispensed if remaining_amount.zero?
choose_next_coin(remaining_amount-->{[25, 10, 5, 1].each{|coin| return coin if remaining_amount >= coin}}.call, coins_dispensed+1)
end
puts "#{choose_next_coin(ARGV.to_i, 0)} coins were dispensed."

To solve for the actual coins, and their quantities, here is a less dense solution:

def choose_biggest_coin(amt)
[25, 10, 5, 1].each do |coin|
return coin if amt >= coin
end
end

def choose_next_coin(remaining_amount, coins_dispensed)
puts "Remaining amount is #{remaining_amount}¢"
return coins_dispensed if remaining_amount.zero?
next_biggest_coin = choose_biggest_coin(remaining_amount)
puts "   reducing it by: #{next_biggest_coin}¢"
choose_next_coin(remaining_amount-next_biggest_coin, coins_dispensed+1)
end

puts "#{choose_next_coin(216, 0)} coins were dispensed."