Determines the fewest coins needed to make up a given amount using a greedy algorithm.

# Coin Change - Greedy Approach # Description: Determines the fewest coins needed to make up a given amount using a greedy algorithm. def coin_change(coins, amount): """ Solve the coin change problem using a greedy algorithm. Determines the minimum number of coins needed to make up a specified amount by selecting the largest possible coins first. Args: coins (list of int): Available coin denominations. amount (int): Target monetary amount to make change for. Returns: list or str: Coins used to make the amount, or "Not possible" if no solution. Key Characteristics: - Prioritizes larger coin denominations - Minimizes total number of coins used - Works perfectly for some coin systems (e.g., US coins) - May fail for certain coin denomination sets Time Complexity: O(n log n), where n is the number of coin denominations Space Complexity: O(amount) Note: Greedy approach is not guaranteed to work for all possible coin sets. """ # Validate input if amount < 0: return "Not possible" # Handle zero amount if amount == 0: return [] # Sort coins in descending order to prioritize larger denominations sorted_coins = sorted(coins, reverse=True) # Coin selection process result = [] remaining = amount # Iterate through coin denominations for coin in sorted_coins: # Use the largest possible coins first while remaining >= coin: result.append(coin) remaining -= coin # Early exit if exact amount is reached if remaining == 0: return result # Check if a complete solution was found return result if remaining == 0 else "Not possible" def coin_change_dynamic_programming(coins, amount): """ Solve the coin change problem using dynamic programming. A more robust approach that guarantees finding the minimum number of coins for any valid set of coin denominations. Args: coins (list of int): Available coin denominations. amount (int): Target monetary amount to make change for. Returns: list or str: Minimum number of coins used, or "Not possible" if no solution. Key Characteristics: - Guaranteed to find the optimal solution - Works for all coin denomination sets - More computationally expensive than greedy approach Time Complexity: O(amount * len(coins)) Space Complexity: O(amount) """ # Validate input if amount < 0: return "Not possible" # Handle zero amount if amount == 0: return [] # Dynamic programming table # dp[i] will store the minimum number of coins for amount i dp = [float('inf')] * (amount + 1) dp[0] = 0 # Track the coins used for each amount coin_used = [[] for _ in range(amount + 1)] # Build solution bottom-up for i in range(1, amount + 1): for coin in coins: if coin

Mar 28, 2025 - 04:49

# Coin Change - Greedy Approach
# Description: Determines the fewest coins needed to make up a given amount using a greedy algorithm.

def coin_change(coins, amount):
    """
    Solve the coin change problem using a greedy algorithm.

    Determines the minimum number of coins needed to make up a specified amount
    by selecting the largest possible coins first.

    Args:
        coins (list of int): Available coin denominations.
        amount (int): Target monetary amount to make change for.

    Returns:
        list or str: Coins used to make the amount, or "Not possible" if no solution.

    Key Characteristics:
    - Prioritizes larger coin denominations
    - Minimizes total number of coins used
    - Works perfectly for some coin systems (e.g., US coins)
    - May fail for certain coin denomination sets

    Time Complexity: O(n log n), where n is the number of coin denominations
    Space Complexity: O(amount)

    Note: Greedy approach is not guaranteed to work for all possible coin sets.
    """
    # Validate input
    if amount < 0:
        return "Not possible"

    # Handle zero amount
    if amount == 0:
        return []

    # Sort coins in descending order to prioritize larger denominations
    sorted_coins = sorted(coins, reverse=True)

    # Coin selection process
    result = []
    remaining = amount

    # Iterate through coin denominations
    for coin in sorted_coins:
        # Use the largest possible coins first
        while remaining >= coin:
            result.append(coin)
            remaining -= coin

        # Early exit if exact amount is reached
        if remaining == 0:
            return result

    # Check if a complete solution was found
    return result if remaining == 0 else "Not possible"

def coin_change_dynamic_programming(coins, amount):
    """
    Solve the coin change problem using dynamic programming.

    A more robust approach that guarantees finding the minimum number of coins
    for any valid set of coin denominations.

    Args:
        coins (list of int): Available coin denominations.
        amount (int): Target monetary amount to make change for.

    Returns:
        list or str: Minimum number of coins used, or "Not possible" if no solution.

    Key Characteristics:
    - Guaranteed to find the optimal solution
    - Works for all coin denomination sets
    - More computationally expensive than greedy approach

    Time Complexity: O(amount * len(coins))
    Space Complexity: O(amount)
    """
    # Validate input
    if amount < 0:
        return "Not possible"

    # Handle zero amount
    if amount == 0:
        return []

    # Dynamic programming table
    # dp[i] will store the minimum number of coins for amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    # Track the coins used for each amount
    coin_used = [[] for _ in range(amount + 1)]

    # Build solution bottom-up
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                # Check if using this coin leads to a better solution
                if dp[i - coin] + 1 < dp[i]:
                    dp[i] = dp[i - coin] + 1
                    coin_used[i] = coin_used[i - coin] + [coin]

    # Return solution or "Not possible"
    return coin_used[amount] if dp[amount] != float('inf') else "Not possible"

# Demonstration function
def demonstrate_coin_change():
    """
    Demonstrate coin change solving with various scenarios.
    """
    test_cases = [
        # US coin denominations
        {
            'coins': [1, 5, 10, 25, 50],
            'amounts': [63, 99, 42]
        },
        # International coin set
        {
            'coins': [1, 2, 5, 10, 20, 50, 100],
            'amounts': [73, 45, 17]
        },
        # Challenging coin set
        {
            'coins': [11, 7, 5],
            'amounts': [15, 22, 33]
        }
    ]

    for case in test_cases:
        coins = case['coins']
        print(f"\nCoin Denominations: {coins}")

        for amount in case['amounts']:
            print(f"\nAmount: {amount}")
            print("Greedy Approach:     ", coin_change(coins, amount))
            print("Dynamic Programming:", coin_change_dynamic_programming(coins, amount))