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[0].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."