Min Number of coins for change

Min Number of coins for change

This solution aims to solve the "minimum number of coins for change" problem, which is a classic dynamic programming problem in computer science.

The problem statement is as follows:

Given an amount n and a list of denominations (coin values), determine the minimum number of coins required to make the amount n using the given denominations. You can use any number of coins of each denomination.

Here's how the solution works:

# O(nd) time | O(n) space where n is the target
def min_number_of_coins_for_change(n, denoms):
    """
    Calculate the minimum number of coins needed to make change for a given amount.

    Args:
        n (int): The target amount for which change needs to be made.
        denoms (list of int): The denominations of coins available for making change.

    Returns:
        int: The minimum number of coins needed to make change for the target amount.
             Returns -1 if it's not possible to make change for the target amount.

    """
    # Handle negative target amount
    if n < 0:
        return -1
    
    # Initialize an array to store the minimum number of coins needed for each amount
    num_of_coins = [float("inf") for amount in range(n + 1)]
    num_of_coins[0] = 0
    
    # Iterate over each denomination
    for denom in denoms:
        # Iterate over each amount from 1 to n
        for amount in range(len(num_of_coins)):
            # Update the minimum number of coins needed for the current amount
            if denom <= amount:
                num_of_coins[amount] = min(num_of_coins[amount], 1 + num_of_coins[amount - denom])
    
    # Return the minimum number of coins needed for the target amount
    return num_of_coins[n] if num_of_coins[n] != float("inf") else -1

Here's how the solution works:

First, I have added a check at the beginning of the function to handle negative target amounts and return -1 immediately to  avoid `IndexError` because the list index is negative

Initialization

Initialize an array num_of_coins of size n+1, where each element represents the minimum number of coins needed to make the corresponding amount from 0 to n.

Initialize all elements to infinity, except for the first element (num_of_coins[0] = 0), which represents the minimum number of coins needed to make 0, i.e., no coins.

Dynamic Programming Iteration

Iterate over each denomination in the list of denominations. For each denomination, iterate over each amount from 0 to n.

If the current denomination is less than or equal to the current amount being considered, update the num_of_coins array at the current amount by taking the minimum between the current value and 1+ the value at the index equal to the current amount minus the denomination.

Result

After completing the iteration, the value at index n in the num_of_coins array represents the minimum number of coins needed to make the amount n using the given denominations.

If the value at index n is still infinity, it means that it's not possible to make the amount n using the given denominations, so return −1 as the result.

Time and Space Complexity

The time complexity of the solution is O(nd), where n is the target amount and d is the number of denominations.

The space complexity is O(n) since we use an array of size n+1 to store the minimum number of coins needed for each amount.

Unit Tests

The unit tests below cover various scenarios:

•     Testing the example given in the prompt.
•     Testing a case where the target amount is not reachable with the given denominations.
•     Testing a case where the target amount is 0.
•     Testing a case where the target amount is already made with a single denomination.
•     Testing a case with a large target amount.
•     Testing a case with denominations having large gaps.
•     Testing a case where the list of denominations is empty.
•     Testing a case where the target amount is negative.

import unittest


class TestMinNumberOfCoinsForChange(unittest.TestCase):
    def test_example_1(self):
        # Test the example given in the prompt
        self.assertEqual(min_number_of_coins_for_change(6, [1, 2, 4]), 2)
    
    def test_example_2(self):
        # Test a case where the target amount is not reachable with the given denominations
        self.assertEqual(min_number_of_coins_for_change(7, [2, 4]), -1)
    
    def test_example_3(self):
        # Test a case where the target amount is 0
        self.assertEqual(min_number_of_coins_for_change(0, [1, 2, 4]), 0)
    
    def test_no_coins_needed(self):
        # Test a case where the target amount is already made with a single denomination
        self.assertEqual(min_number_of_coins_for_change(10, [10]), 1)
    
    def test_large_amount(self):
        # Test a case with a large target amount
        self.assertEqual(min_number_of_coins_for_change(100, [1, 5, 10, 25]), 4)
    
    def test_denominations_with_large_gaps(self):
        # Test a case with denominations having large gaps
        self.assertEqual(min_number_of_coins_for_change(12, [1, 5, 10, 25]), 3)
    
    def test_empty_denominations(self):
        # Test a case where the list of denominations is empty
        self.assertEqual(min_number_of_coins_for_change(5, []), -1)
    
    def test_negative_amount(self):
        # Test a case where the target amount is negative
        self.assertTrue(min_number_of_coins_for_change(-5, [1, 2, 4]), -1)


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