Make Change

gistfile1.rb

def greedy_make_change(num)
  denominations = [50, 25, 10, 1]
  change = []
  while num > 0
    denominations.each do |denomination|
      if num - denomination >= 0
        num -= denomination
        change << denomination
        break
      end
    end
  end
  change
end
p greedy_make_change(56)

def charitable_make_change(num)
  return [] if num == 0
  denominations = [50, 25, 10, 1]
  options = denominations.map do |denomination|
    remainder = num - denomination
    [denomination, *charitable_make_change(remainder)] if remainder >= 0
  end
  options.compact.sort_by(&:size)[0]
end
p charitable_make_change(30)