count_coins.py

#  3 ways to give change for 4
#  with denomination 1 and 2
# 1+1+1+1, 1+1+2, 2+2.
# 
# 1+1+2 == 2+1+1

#   count_change(4, [1,2]) # => 3
#   count_change(10, [5,2,3]) # => 4
#   count_change(11, [5,7]) # => 0

def count_change(money, coins):
    """ Determine how many different ways you can make change for an amount of money,
    given an array of coin denominations.
    
    This function has a complexity of O(m*n), where m is the value of money
    and n is the number of unique different coins available
    """
    if money == 0:
        return 1
    
    # sort coins in ascending order
    # this makes it mapped to the indices of the rows in table
    # eg: [2, 3, 5, 11] -> [row0, row1, row2, row4]
    # we can thus enumerate coins_map and get both row-indices and associated coins
    coins_map = sorted(
      coin
      for coin in coins \
        # coins bigger than the money or negative, will be neglected
        if coin <= money and coin > 0
    )
    
    # remove any duplicates from coins, since order does not matter
    coins_map = tuple(set(coins_map))
    
    # no coins means we cant give any change. Same goes for negative money
    if not coins_map or money < 0:
        return 0

    # compute different ways of giving change, starting from smaller coins
    table = tuple(
        [0 for _ in range(money+1)]
        for _ in coins_map
    )
    for i, coin in enumerate(coins_map):
        for j in range(money+1):
            # get number of times, we can give change for smaller coins than the current one
            if i == 0:
                # edge case
                if j == 0:
                    smaller_coins_count = 1
                elif coin <= j and not (j % coin):
                    smaller_coins_count = 1
                else:
                    smaller_coins_count = 0
            else:
                smaller_coins_count = table[i-1][j]

            # get number of times we can give change only current coin were available
            if i == 0 or coin > j:
                curr_coin_only_count = 0
            else:
                curr_coin_only_count = table[i][j - coin]

            table[i][j] = smaller_coins_count + curr_coin_only_count
    
    # the answer is the way of giving change for the biggest coin and amount, in table
    return table[-1][-1]

if __name__ == "__main__":
    print(count_change(5, [1, 2, 3]))