Skip to content

Day 11 - Coin Change (Count Ways).md

Latest commit

 

History

History
227 lines (185 loc) · 6.81 KB

Day 11 - Coin Change (Count Ways).md

File metadata and controls

227 lines (185 loc) · 6.81 KB
Raw
Difficulty Medium
Source 160 Days of Problem Solving
Tags
Dynamic Programming
Arrays

🚀 Day 11. Coin Change (Count Ways) 🧠

The problem can be found at the following link: Question Link

💡 Problem Description:

Given an integer array coins[] representing different denominations of currency and an integer sum, find the number of ways to make sum using any number of coins.
🔹 Note: You have an infinite supply of each type of coin.

🔍 Example Walkthrough:

Example 1:

Input:

coins = [1, 2, 3], sum = 4

Output:

4

Explanation:

There are 4 ways to make 4 using given coins:

  1. [1, 1, 1, 1]
  2. [1, 1, 2]
  3. [2, 2]
  4. [1, 3]

Example 2:

Input:

coins = [2, 5, 3, 6], sum = 10

Output:

5

Explanation:

There are 5 ways to make 10:

  1. [2, 2, 2, 2, 2]
  2. [2, 2, 3, 3]
  3. [2, 2, 6]
  4. [2, 3, 5]
  5. [5, 5]

Constraints:

  • $1 \leq \text{Number of Coins} \leq 10^3$
  • $1 \leq \text{sum} \leq 10^6$
  • $1 \leq \text{coins}[i] \leq 10^3$

🎯 My Approach:

Optimized Dynamic Programming

Algorithm Steps:

  1. Use a 1D DP array dp[], where dp[i] stores the number of ways to make sum i.
  2. Base Case:
    • dp[0] = 1 (There is one way to make sum 0: choose nothing).
  3. Transition:
    • For each coin, update all sums from coin to sum.
    • dp[j] += dp[j - coin] (Include current coin).

🕒 Time and Auxiliary Space Complexity

  • Expected Time Complexity: O(N × sum), where N is the number of coins.
  • Expected Auxiliary Space Complexity: O(sum), as we only store a 1D DP array.

📝 Solution Code

Code (C++)

class Solution {
  public:
    int count(vector<int>& coins, int sum) {
        vector<int> dp(sum + 1, 0);
        dp[0] = 1;
        for (int coin : coins)
            for (int j = coin; j <= sum; j++)
                dp[j] += dp[j - coin];
        return dp[sum];
    }
};

⚡ Alternative Approaches

2️⃣ Dynamic Programming (O(N×sum) Time, O(N×sum) Space) — 2D DP

Algorithm Steps:

  1. Use a 2D DP table where dp[i][j] represents the number of ways to make sum j using the first i coins.
  2. Base Case:
    • dp[0][0] = 1 (one way to make sum 0 with zero coins).
    • dp[i][0] = 1 for all i (only one way to make sum 0: choose nothing).
  3. Recurrence Relation:
    $[ \text{dp}[i][j] = \text{dp}[i-1][j] + \text{dp}[i][j - \text{coins}[i-1]] $]
    • Exclude the coin (dp[i-1][j]).
    • Include the coin (dp[i][j - coins[i-1]]).
class Solution {
  public:
    int count(vector<int>& coins, int sum) {
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(sum + 1, 0));
        for (int i = 0; i <= n; i++) dp[i][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= sum; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i - 1]) dp[i][j] += dp[i][j - coins[i - 1]];
            }
        }
        return dp[n][sum];
    }
};

✅ Time Complexity: O(N × sum)
✅ Space Complexity: O(N × sum)

3️⃣ Recursive + Memoization (O(N×sum) Time, O(N×sum) Space)

Algorithm Steps:

  1. Recursive function countWays(index, sum) calculates the number of ways using coins up to index.
  2. Base Case:
    • If sum == 0, return 1 (valid way found).
    • If index < 0 or sum < 0, return 0 (invalid case).
  3. Recurrence Relation:
    $[ \text{countWays(index, sum)} = \text{countWays(index - 1, sum)} + \text{countWays(index, sum - coins[index])} $]
    • Exclude the current coin.
    • Include the current coin.
  4. Use memoization (dp[index][sum]) to avoid redundant calculations.
class Solution {
  public:
    vector<vector<int>> dp;
    int solve(vector<int>& coins, int i, int sum) {
        if (sum == 0) return 1;
        if (i < 0 || sum < 0) return 0;
        if (dp[i][sum] != -1) return dp[i][sum];
        return dp[i][sum] = solve(coins, i - 1, sum) + solve(coins, i, sum - coins[i]);
    }

    int count(vector<int>& coins, int sum) {
        int n = coins.size();
        dp.assign(n, vector<int>(sum + 1, -1));
        return solve(coins, n - 1, sum);
    }
};

✅ Time Complexity: O(N × sum)
✅ Space Complexity: O(N × sum)

Comparison of Approaches

Approach ⏱️ Time Complexity 🗂️ Space Complexity ✅ Pros ⚠️ Cons
1D Space Optimized DP 🟡 O(N × sum) 🟢 O(sum) Most efficient space-wise Requires careful indexing
2D DP (Tabulation) 🟡 O(N × sum) 🔴 O(N × sum) Easy to implement, intuitive High space usage
Recursive + Memoization 🟡 O(N × sum) 🔴 O(N × sum) Natural recursion flow Stack overhead

✅ Best Choice?

  • If optimizing space: Use 1D DP (Space-Optimized).
  • If space is not a concern: Use 2D DP (Tabulation) for easy understanding.
  • For recursion lovers: Use Recursive + Memoization.

Code (Java)

class Solution {
    public int count(int[] coins, int sum) {
        int[] dp = new int[sum + 1];
        dp[0] = 1;
        for (int coin : coins)
            for (int j = coin; j <= sum; j++)
                dp[j] += dp[j - coin];
        return dp[sum];
    }
}

Code (Python)

class Solution:
    def count(self, coins, sum):
        dp = [0] * (sum + 1)
        dp[0] = 1
        for coin in coins:
            for j in range(coin, sum + 1):
                dp[j] += dp[j - coin]
        return dp[sum]

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count