Coin Change – Python Coding Challenges

Coin Change – Python Coding Challenges

When you visit a shop and need to pay a certain amount using the fewest coins possible, you’re actually solving a Coin Change problem — a classic Dynamic Programming (DP) challenge used in real-world systems and coding interviews. This problem is an excellent way to improve your DP and array manipulation skills.

💡 Problem Understanding

You are given:

• An array coins[] representing available denominations.
• An integer amount representing the total value you need to make.

Find the minimum number of coins needed to make up the amount. If it’s not possible, return -1.

🧠 Example

coins = [1, 2, 5]
amount = 11
# Output: 3
# Explanation: 11 = 5 + 5 + 1

⚙️ Approach 1: Brute Force (Recursive)

def coinChange(coins, amount):
    if amount == 0:
        return 0
    if amount < 0:
        return -1

    min_coins = float('inf')
    for coin in coins:
        res = coinChange(coins, amount - coin)
        if res >= 0:
            min_coins = min(min_coins, 1 + res)
    return min_coins if min_coins != float('inf') else -1
    print(coinChange(coins, amount))

Problem: The above solution is slow because it recomputes subproblems multiple times. Time complexity: O(2^n).

⚡ Approach 2: Dynamic Programming (Bottom-Up)

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1
     print(coinChange(coins, amount))

Step-by-Step DP Table

Amount	dp[i]	Explanation
0	0	No coins needed
1	1	One coin of 1
2	1	One coin of 2
3	2	1 + 2
5	1	One coin of 5
11	3	5 + 5 + 1

⏱️ Complexity

• Time: O(n × amount)
• Space: O(amount)

🧰 Alternate Variation – Coin Change 2 (Total Combinations)

def countWays(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]
    print(countWays(coins, amount))

Example: For coins = [1, 2, 5] and amount = 5, Output → 4 (ways: 5, 2+2+1, 2+1+1+1, 1+1+1+1+1)

🧑‍💻 Try It Yourself – Tasks for Practice

• Modify the function to print which coins were used to make the amount.
• Handle floating-point coin denominations like ₹0.5 or ₹2.5.
• For coins = [2, 4] and amount = 7, find the result.
• Use the countWays function for coins = [1, 3, 4] and amount = 6.

📚 Real-World Use Cases

• Optimizing currency distribution in digital wallets.
• ATM cash dispensing algorithms.
• Inventory or resource allocation optimization.

❓ Frequently Asked Questions (FAQ)

Q1: Why use Dynamic Programming instead of recursion?

DP avoids recomputation by storing results of subproblems, improving efficiency.

Q2: What if all coins are greater than the amount?

The function returns -1 since no valid combination exists.

Q3: Can we solve this using a Greedy approach?

Only for specific coin systems like U.S. currency. DP works universally.

Q4: How to handle very large amounts?

Use the bottom-up DP approach with optimized space usage.

Q5: Is this asked in interviews?

Yes! The Coin Change problem is a popular Dynamic Programming interview question.

🏁 Conclusion

The Coin Change Problem is more than just a math puzzle — it teaches the essence of breaking down complex problems into smaller manageable parts using Dynamic Programming. A must-practice for any Python developer or interviewee.

Next Blog: 👉 Longest Common Prefix – Python Coding Challenges