Algorithms for Coding Interviews in Python/

...

/

Solution: The Coin Change Problem

Solution: The Coin Change Problem

This review provides a detailed analysis of the different ways to solve the coin change problem.

We'll cover the following...

Solution 1: brute force

Python 3.5
def count_change(denoms, denoms_length, amount):
    """
    Finds the number of ways that the given number of cents can be represented.
    :param denoms: Values of the coins available
    :param amount: Given cent
    :return: The number of ways that the given number of cents can be represented.
    """
    # If n is 0 then there is 1 solution
    # (do not include any coin)
    if amount == 0:
        return 1
    # If n is less than 0 then no
    # solution exists
    if amount < 0 or denoms_length <= 0:
        return 0
    # If there are no coins and n
    # is greater than 0, then no
    # solution exist
    if denoms_length <= 0 and amount >= 1:
        return 0
    # Count is sum of solutions
    # (i) including denoms[len(denoms) - 1]
    # (ii) excluding denoms[len(denoms) - 1]
    return count_change(denoms, denoms_length - 1, amount) + count_change(denoms, denoms_length, amount - denoms[denoms_length - 1])
# Driver code to test the above function
if __name__ == '__main__':
    denoms = [25, 10, 5, 1]
    print(count_change(denoms, len(denoms), 10))

Explanation

To count the total number of solutions, we divide the solution into two sets:

  1. Solutions that do not contain mthm^{th} denomination (or denoms[denoms_length - 1])
  2. Solutions that contain at least one denoms[denoms_length - 1]

However, notice that the function recomputes the same subproblem several times (line 28).

Time complexity

The time complexity of this solution is in O(2denomslength)O(2^{denomslength}). Why? This is because for every coin, we have 2 options: either include it or exclude it. If we think in terms of binary, it’s 0 to exclude and 1 to include. For example, if we have 2 coins, the options will be 00, 01, 10, 11 which is 4 or 222^2 options. So, extrapolating that to ...