Minimum coins algorithm in Ruby I am working on a puzzle to find the minimum number of coins needed to buy a product.

I am given three coins:


1
3
5


and also a number representing the price of a product:


11


The answer here would be three, since it takes at least three coins to reach this number.

5, 5, 1


I decided it was best to use Ruby's repeated_permutation method. I tested my method in irb and it seems to work for smaller inputs, but when I submitted it to the online grader, I got a Memory Allocation Error.

File.open(ARGV[0]).each_line do |line|
    number = line.to_i
    coins = [1,3,5]
    coin_combos = []
    i = 1
    until coin_combos.flatten(1).any? { |c| c.inject(:+) &gt;= number }
        coin_combos &lt;&lt; coins.repeated_permutation(i).to_a
        i += 1
    end
    puts i - 1
end


Here was my thought process:


Store the different types of coins in a coins array
Initialize an empty array for storing sequences of coins
Use a loop. It will be finished once the sum of one of the sequences is equal to or surpasses the product's price.
Push to my array the number of repeated permutations of length equal to my counter
Increment my counter and test for the condition again


This seems to be a problem with my algorithm and I'm using up too much space here.

Is there a different algorithm I should use?
I don't see why you need to calculate permutations. Simply calculate the quotient and remainder of the division starting from the highest coins. In imperative style:

def get_num_coins(coins, value)
  ncoins = 0
  coins.sort.reverse.each do |coin|
    ncoins +=  value / coin
    value = value % coin
  end
  ncoins
end


In functional style:

def get_num_coins(coins, value)
  coins.sort.reverse.reduce(value: value, ncoins: 0) do |state, coin|
    q, r = state[:value].divmod(coin)
    {value: r, ncoins: state[:ncoins] + q}
  end.fetch(:ncoins)
end