change_maker.rb

# Not thoroughly tested, but this seems to solve the problem recursively

class ChangeMaker
  
  # in cents, so the below ints are equal to
  # penny, nickle, dime, quarter, dollar, five, ten, twenty, fifty, a hundred
  
  DENOMINATIONS = [1, 5, 10, 25, 100, 500, 1000, 2000, 5000, 10000]
  
  def initialize(cost, tendered)
    @cost = cost
    @tendered = tendered
    @difference = tendered - cost
    @change ||= Hash.new(0)
  end
  
  def calculate_difference(n=-1)
    return nil if @difference < 0
    return @change if @difference == 0
    subtract_from_difference(n)
    calculate_difference(n-1)
  end
  
  def subtract_from_difference(n)
    return if @difference < DENOMINATIONS[n]
    @change[DENOMINATIONS[n]] += 1
    @difference -= DENOMINATIONS[n]
    subtract_from_difference(n)
  end
  
end

maker = ChangeMaker.new(1000, 5999)
p maker.calculate_difference 

maker = ChangeMaker.new(1, 90000)
p maker.calculate_difference 

# >> {2000=>2, 500=>1, 100=>4, 25=>3, 10=>2, 1=>4}
# >> {10000=>8, 5000=>1, 2000=>2, 500=>1, 100=>4, 25=>3, 10=>2, 1=>4}