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(:+) >= number }
        coin_combos << 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

StackExchange Code Review Q#86925, answer score: 6