How to calculate the number of ways to represent n cents

This question already has an answer here:

  • How to find all combinations of coins when given some dollar value

    32 answers

  • Rails creating an event for a user
  • Shoes and Gems
  • How to call expire_fragment from Rails Observer/Model?
  • Rails Assets in Production
  • int((0.1+0.7)*10) = 7 in several languages. How to prevent this?
  • `autoload` raises an error but `require` does not (ruby)
  • How can I make a gem perform an action on install?
  • Delete all non cyrullic symbols from string
  • 3 Solutions collect form web for “How to calculate the number of ways to represent n cents”

    We can see if your code is correct quite easily. let’s try making change for a dime. There are three ways: 1 dime, 1 nickel and 5 pennies, and 10 pennies, yet count_ways(10) #=> 9.

    You can do it as follows, using recursion.

    Code

    def count_ways(cents, coins)
      if coins.size == 1
        return (cents % coins.first) == 0 ? [cents/coins.first] : nil
      end 
      coin, *remaining_coins = coins
      (0..cents/coin).each_with_object([]) { |n, arr|
        count_ways(cents-n*coin, remaining_coins).each { |a| arr << [n, *a] } }
    end 
    

    Examples

    coins = [25, 10, 5, 1]
    
    count_ways(32, coins)
      #=> [[0, 0, 0, 32], [0, 0, 1, 27], [0, 0, 2, 22], [0, 0, 3, 17], [0, 0, 4, 12],
      #    [0, 0, 5,  7], [0, 0, 6,  2], [0, 1, 0, 22], [0, 1, 1, 17], [0, 1, 2, 12],
      #    [0, 1, 3,  7], [0, 1, 4,  2], [0, 2, 0, 12], [0, 2, 1,  7], [0, 2, 2,  2],
      #    [0, 3, 0,  2], [1, 0, 0,  7], [1, 0, 1,  2]] 
    
    count_ways(100, coins)
      #=> [[0, 0, 0, 100], [0, 0, 1, 95], [0, 0, 2, 90], [0, 0, 3, 85], [0, 0, 4, 80],
      #    [0, 0, 5,  75], [0, 0, 6, 70], [0, 0, 7, 65], [0, 0, 8, 60], [0, 0, 9, 55],
      #    ...
      #    [3, 1, 2,   5], [3, 1, 3,  0], [3, 2, 0,  5], [3, 2, 1,  0], [4, 0, 0,  0]] 
    count_ways(100, coins).size
      #=> 242 
    

    Explanation

    The best way to show how the recursion works is to salt the code with puts statements and then run it against a simple example.

    INDENT = 8
    @indentation = 0
    
    def indent
     @indentation += INDENT
    end
    
    def undent
     @indentation = [@indentation-INDENT, 0].max
    end
    
    def ind
      ' '*@indentation
    end
    

    def count_ways(cents, coins)
      puts "#{ind}** entering count_ways with cents=#{cents}, coins=#{coins}"
      if coins.size == 1
        puts "#{ind}<< returning [cents]=#{[cents]} as coins.size == 1" 
        undent
      end  
      return [cents] if coins.size == 1
      coin, *remaining_coins = coins
      puts "#{ind}coin=#{coin}. remaining_coins=#{remaining_coins}"
      puts "#{ind}0..cents/coin=#{0..cents/coin}"
      arr = (0..cents/coin).each_with_object([]) do |n, arr|
        puts "#{ind}  n=#{n}, arr=#{arr}"
        puts "#{ind}  >> calling count_ways(#{cents}-#{n}*#{coin}, remaining_coins)"
        indent
        aa = count_ways(cents-n*coin, remaining_coins)
        puts "#{ind}  aa=#{aa}"
        aa.each do |a|
          arr << [n, *a]
          puts "#{ind}    arr << [#{n}, *#{a}], arr=#{arr}"
        end
        puts "#{ind}  after all coins, arr=#{arr}"
      end
      puts "#{ind}<< returning arr=#{arr}"
      undent
      arr
    end
    

    Now let’s run count_ways(12, coins) which should return the four ways of making change for 12 cents: [[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]].

    count_ways(12, coins)
    ** entering count_ways with cents=12, coins=[25, 10, 5, 1]
    coin=25. remaining_coins=[10, 5, 1]
    0..cents/coin=0..0
      n=0, arr=[]
      >> calling count_ways(12-0*25, remaining_coins)
            ** entering count_ways with cents=12, coins=[10, 5, 1]
            coin=10. remaining_coins=[5, 1]
            0..cents/coin=0..1
              n=0, arr=[]
              >> calling count_ways(12-0*10, remaining_coins)
                    ** entering count_ways with cents=12, coins=[5, 1]
                    coin=5. remaining_coins=[1]
                    0..cents/coin=0..2
                      n=0, arr=[]
                      >> calling count_ways(12-0*5, remaining_coins)
                            ** entering count_ways with cents=12, coins=[1]
                            << returning [cents]=[12] as coins.size == 1
    

                      aa=[12]
                        arr << [0, *12], arr=[[0, 12]]
                      after all coins, arr=[[0, 12]]
                      n=1, arr=[[0, 12]]
                      >> calling count_ways(12-1*5, remaining_coins)
                            ** entering count_ways with cents=7, coins=[1]
                            << returning [cents]=[7] as coins.size == 1
                      aa=[7]
                        arr << [1, *7], arr=[[0, 12], [1, 7]]
                      after all coins, arr=[[0, 12], [1, 7]]
                      n=2, arr=[[0, 12], [1, 7]]
                      >> calling count_ways(12-2*5, remaining_coins)
                            ** entering count_ways with cents=2, coins=[1]
                            << returning [cents]=[2] as coins.size == 1
    

                      aa=[2]
                        arr << [2, *2], arr=[[0, 12], [1, 7], [2, 2]]
                      after all coins, arr=[[0, 12], [1, 7], [2, 2]]
                    << returning arr=[[0, 12], [1, 7], [2, 2]]
              aa=[[0, 12], [1, 7], [2, 2]]
                arr << [0, *[0, 12]], arr=[[0, 0, 12]]
                arr << [0, *[1, 7]], arr=[[0, 0, 12], [0, 1, 7]]
                arr << [0, *[2, 2]], arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2]]
              after all coins, arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2]]
              n=1, arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2]]
              >> calling count_ways(12-1*10, remaining_coins)
                    ** entering count_ways with cents=2, coins=[5, 1]
                    coin=5. remaining_coins=[1]
                    0..cents/coin=0..0
                      n=0, arr=[]
                      >> calling count_ways(2-0*5, remaining_coins)
                            ** entering count_ways with cents=2, coins=[1]
                            << returning [cents]=[2] as coins.size == 1
    

                      aa=[2]
                        arr << [0, *2], arr=[[0, 2]]
                      after all coins, arr=[[0, 2]]
                    << returning arr=[[0, 2]]
              aa=[[0, 2]]
                arr << [1, *[0, 2]], arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]]
              after all coins, arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]]
            << returning arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]]
      aa=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]]
        arr << [0, *[0, 0, 12]], arr=[[0, 0, 0, 12]]
        arr << [0, *[0, 1, 7]], arr=[[0, 0, 0, 12], [0, 0, 1, 7]]
        arr << [0, *[0, 2, 2]], arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2]]
        arr << [0, *[1, 0, 2]], arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]]
      after all coins, arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]]
    << returning arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]]
     => [[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]] 
    

    No, you will be double-counting solutions, because you could first pick a quarter and then a dime or the other way around, but those solutions are essentially the same.

    The easiest way to prevent double-counting is to make sure you never pick a coin that is bigger than the ones you already picked.

    In code:

    def count_ways(n, max_coin)
      return 0 if n < 0 
      return 1 if n == 0 
    
      result = count_ways(n-1, 1)
      result = result + count_ways(n- 5,  5) if max_coin >=  5
      result = result + count_ways(n-10, 10) if max_coin >= 10
      result = result + count_ways(n-25, 25) if max_coin >= 25
      result
    end
    

    And call it with 25 as initial max coin

    The order of the coins doesn’t matter, so coins.min isn’t going to help you in this case – it’s over-complicating things.

    First we must develop an intuition about the relationship between the kinds of coins and the amount of change to count

    The number of ways to change amount a using n kinds of coins equals

    • the number of ways to change amount a using all but the first kind of coin, plus
    • the number of ways to change amount a − d using all n kinds of coins, where d is the denomination of the first kind of coin.

    source: SICP Chapter 1.2

    ### change_coins :: (Int, [Int]) -> Int
    def change_coins amount, (x,*xs)
      if amount == 0
        1
      elsif amount < 0 or x.nil?
        0
      else
        change_coins(amount, xs) + change_coins(amount - x, [x,*xs])
      end
    end
    
    change_coins 11, [1, 2, 5]           # => 11
    change_coins 2, [3]                  # => 0
    change_coins 100, [1, 5, 10, 25, 50] # => 292
    

    Sensible return values

    For example, in this problem we have to return -1 if the amount of money cannot be made up by any combination of the coins.

    The -1 case is dumb. There are zero ways to change 2 cents using only a 3-cent coin; therefore we return 0.

    If you really must return -1, just use a stupid wrapper

    def cc amount, xs
      count = change_coins amount, xs
      if count == 0 then -1 else count end
    end
    

    Order doesn’t matter

    change_coins 11, [5, 1, 2]           # => 11
    change_coins 2, [3]                  # => 0
    change_coins 100, [50, 1, 25, 10, 5] # => 292
    
    Ruby is the best programming language in the world - Ruby on Rails.