Number of Ways to make Change

This solution seeks to solve the problem of finding the number of ways to make change for a given amount of money n using a given set of coin denominations denoms.

First, here is a representation of how I arrived at 4 for a target of 10 with the following set of coin denominations: [1, 5, 10, 25]

ways->											4
ways->						2	2	2	2	2	3
ways->		1	1	1	1	1	1	1	1	1	1
ways->	1	0	0	0	0	0	0	0	0	0	0
denom->	0	1	2	3	4	5	6	7	8	9	10

Now, here is the code implementation.

# O(nd) time | O (n) space
def number_of_ways_to_make_change(n, denoms):
	ways =[0 for amount in range(n+1)] # [0] * (n + 1)
	ways[0] =1 #if we have 0 as our target amount,then there is only one way of getting 0 which is not using any coin
	for denom in denoms:
		for amount in range(1, n+1):
			if denom <= amount:
				ways[amount] += ways[amount-denom]
	return ways[n]
	
print(f"number_of_ways_to_make_change :: {number_of_ways_to_make_change(10, [1, 5, 10, 25])}")

Here's what's happening in the solution:

• The function number_of_ways_to_make_change takes two parameters: n (the target amount for which change needs to be made) and denoms (a list of coin denominations available for making change).
• It initializes an array ways of size n+1 with all elements set to 0. This array will store the number of ways to make change for each amount from 0 to n.
• It sets ways[0] to 1 because there is exactly one way to make change for an amount of 0, which is by using no coins.
• It iterates over each denomination in the denoms list.
• For each denomination, it iterates over each amount from 1 to n (inclusive).
• For each amount, it checks if the denomination is less than or equal to the current amount. If it is, it means that the current denomination can be used to make change for the current amount.
•  If the denomination is less than or equal to the current amount, it updates ways[amount] by adding the value of ways[amount - denom]. This is because the number of ways to make change for the current amount using the current denomination is equal to the number of ways to make change for the amount - denom (the remaining amount after subtracting the denomination) plus the number of ways to make change for the remaining amount using the same denomination.
• Finally, the function returns ways[n], which represents the number of ways to make change for the target amount n using the given coin denominations.

For example, if n = 10 and denoms = [1, 5, 10, 25], the function will return the number of ways to make change for 10 cents using the given denominations.

Time Complexity

The solution consists of a nested loop structure.

• The outer loop iterates over each denomination in the denoms list, which has d denominations.
• The inner loop iterates over each amount from 1 to n, where n is the target amount.
• Inside the inner loop, the operations performed are constant time operations (assignment, comparison, and addition).
• Therefore, the time complexity of the solution is O(nd), where n is the target amount and d is the number of denominations.

Space Complexity

The solution uses an array of ways of size n+1 to store the number of ways to make change for each amount from 0 to n leading to O(n) space complexity.

Unit Tests

Here are some unit tests to verify the correctness of the number_of_ways_to_make_change function:

import unittest

class TestNumberOfWaysToMakeChange(unittest.TestCase):
    def test_example_1(self):
        n = 10
        denoms = [1, 5, 10, 25]
        self.assertEqual(number_of_ways_to_make_change(n, denoms), 4)

    def test_example_2(self):
        n = 5
        denoms = [1, 2, 5]
        self.assertEqual(number_of_ways_to_make_change(n, denoms), 4)

    def test_example_3(self):
        n = 0
        denoms = [1, 2, 5]
        self.assertEqual(number_of_ways_to_make_change(n, denoms), 1)

    def test_example_4(self):
        n = 3
        denoms = [2]
        self.assertEqual(number_of_ways_to_make_change(n, denoms), 0)

    def test_example_5(self):
        n = 4
        denoms = [1, 2, 3]
        self.assertEqual(number_of_ways_to_make_change(n, denoms), 4)

    def test_large_input(self):
        # Test with a large target amount and denominations
        n = 100
        denoms = [1, 5, 10, 25, 50]
        # There are 292 ways to make change for 100 cents using the given denominations
        self.assertEqual(number_of_ways_to_make_change(n, denoms), 292)

if __name__ == '__main__':
    unittest.main()

These test cases cover various scenarios, including:

•     Making change for different target amounts.
•     Using different sets of denominations.
•     Handling edge cases like making change for 0 cents or using a single denomination.