Coin Change Minimum Coins in DSA C

Mental Model

Find the smallest number of coins needed to make a target amount using given coin values. We build up solutions from smaller amounts to the target.

Analogy: Imagine you want to pay a certain amount using coins from your wallet. You try to use the fewest coins possible by checking all smaller amounts first, like climbing stairs one step at a time.

coins: [1, 3, 4]
amount: 6
DP array indices: 0 1 2 3 4 5 6
DP values:       0 ∞ ∞ ∞ ∞ ∞ ∞
(∞ means not yet computed)

Dry Run Walkthrough

Input: coins: [1, 3, 4], amount: 6

Goal: Find the minimum number of coins needed to make amount 6

Step 1: Initialize DP array with 0 for amount 0 and infinity for others

DP: [0, ∞, ∞, ∞, ∞, ∞, ∞]

Why: Base case: 0 coins needed to make amount 0

Step 2: Calculate minimum coins for amount 1 using coins

DP: [0, 1, ∞, ∞, ∞, ∞, ∞]

Why: Using coin 1, min coins for 1 is 1

Step 3: Calculate minimum coins for amount 2

DP: [0, 1, 2, ∞, ∞, ∞, ∞]

Why: Using coin 1 twice, min coins for 2 is 2

Step 4: Calculate minimum coins for amount 3

DP: [0, 1, 2, 1, ∞, ∞, ∞]

Why: Using coin 3 once, min coins for 3 is 1

Step 5: Calculate minimum coins for amount 4

DP: [0, 1, 2, 1, 1, ∞, ∞]

Why: Using coin 4 once, min coins for 4 is 1

Step 6: Calculate minimum coins for amount 5

DP: [0, 1, 2, 1, 1, 2, ∞]

Why: Using coin 1 + min coins for 4 (1), total 2

Step 7: Calculate minimum coins for amount 6

DP: [0, 1, 2, 1, 1, 2, 2]

Why: Using coin 3 + min coins for 3 (1), total 2

Result:

DP: [0, 1, 2, 1, 1, 2, 2]
Minimum coins needed: 2

Annotated Code

DSA C

#include <stdio.h>
#include <limits.h>

int minCoins(int coins[], int n, int amount) {
    int dp[amount + 1];
    dp[0] = 0; // base case

    for (int i = 1; i <= amount; i++) {
        dp[i] = INT_MAX; // initialize with infinity
        for (int j = 0; j < n; j++) {
            if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
                int sub_res = dp[i - coins[j]] + 1;
                if (sub_res < dp[i]) {
                    dp[i] = sub_res; // update min coins for amount i
                }
            }
        }
    }

    if (dp[amount] == INT_MAX) {
        return -1; // no solution
    }
    return dp[amount];
}

int main() {
    int coins[] = {1, 3, 4};
    int amount = 6;
    int n = sizeof(coins) / sizeof(coins[0]);

    int result = minCoins(coins, n, amount);
    if (result == -1) {
        printf("No solution\n");
    } else {
        printf("Minimum coins needed: %d\n", result);
    }
    return 0;
}

dp[0] = 0; // base case

Set 0 coins needed to make amount 0

dp[i] = INT_MAX; // initialize with infinity

Start with no known solution for amount i

if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {

Check if coin can be used and subproblem has solution

dp[i] = sub_res; // update min coins for amount i

Update dp[i] if using coin j leads to fewer coins

if (dp[amount] == INT_MAX) return -1;

Return -1 if no combination can make amount

Output

Minimum coins needed: 2

Complexity Analysis

Time: O(n * amount) because we compute minimum coins for each amount up to target, checking all coins

Space: O(amount) for the dp array storing minimum coins for each amount

vs Alternative: Compared to recursive brute force exponential time, this dynamic programming approach is efficient and avoids repeated calculations

Edge Cases

amount is 0

Returns 0 immediately since no coins are needed

DSA C

dp[0] = 0; // base case

no coins can make the amount

Returns -1 indicating no solution

DSA C

if (dp[amount] == INT_MAX) return -1;

coins array empty

Returns -1 since no coins available to form amount

DSA C

if (dp[amount] == INT_MAX) return -1;

When to Use This Pattern

When asked for the fewest items to reach a total from given options, use the Coin Change Minimum Coins pattern with dynamic programming to build solutions from smaller totals.

Common Mistakes

Mistake: Not initializing dp array properly leading to incorrect minimum calculations
Fix: Initialize dp[i] with a large number (infinity) before updating with minimum values

Mistake: Not checking if subproblem dp[i - coin] is solvable before adding 1
Fix: Add condition to skip if dp[i - coin] is infinity (no solution)

Summary

Finds the minimum number of coins needed to make a target amount from given coin denominations.

Use when you want the smallest count of coins to form a specific amount.

Build the solution bottom-up by solving smaller amounts first and using those results to solve bigger amounts.

Practice

1. What does the Coin Change Minimum Coins problem ask you to find?

easy

A. The smallest number of coins needed to make a given amount

B. The total number of different coins available

C. The largest coin value in the set

D. The total sum of all coin values

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum number of coins needed to make a specific amount using given coin denominations.

2. Step 2: Identify the correct description

   The smallest number of coins needed to make a given amount correctly describes this goal, while others describe unrelated concepts.

3. Final Answer:

   The smallest number of coins needed to make a given amount -> Option A

4. Quick Check:

   Minimum coins = smallest count needed [OK]

Hint: Focus on 'minimum coins' needed to form the amount [OK]

Common Mistakes:

• Confusing total coin count with minimum coins
• Thinking about coin values instead of counts
• Mixing up largest coin with minimum coins

2. Which of the following is the correct way to initialize the DP array for the Coin Change Minimum Coins problem in C?

easy

A. int dp[amount+1]; for(int i=0; i<=amount; i++) dp[i] = 0;

B. int dp[amount+1]; for(int i=0; i<=amount; i++) dp[i] = -1;

C. int dp[amount+1] = {0};

D. int dp[amount+1]; for(int i=0; i<=amount; i++) dp[i] = INT_MAX;

Solution

1. Step 1: Understand DP initialization

   We initialize dp array with a large number (like INT_MAX) to represent impossible states initially.

2. Step 2: Identify correct initialization

   int dp[amount+1]; for(int i=0; i<=amount; i++) dp[i] = INT_MAX; correctly sets all dp values to INT_MAX, except dp[0] which is usually set to 0 later.

3. Final Answer:

   int dp[amount+1]; for(int i=0; i<=amount; i++) dp[i] = INT_MAX; -> Option D

4. Quick Check:

   Initialize dp with max values for minimum search [OK]

Hint: Use INT_MAX to mark unreachable amounts initially [OK]

Common Mistakes:

• Initializing dp with zeros causes wrong minimum calculations
• Using -1 without handling leads to errors
• Not setting dp[0] = 0 explicitly

3. What is the output of the following code snippet for coins = {1, 3, 4} and amount = 6?

int coins[] = {1, 3, 4};
int amount = 6;
int dp[7];
for(int i=0; i<=amount; i++) dp[i] = amount+1;
dp[0] = 0;
for(int i=1; i<=amount; i++) {
  for(int j=0; j<3; j++) {
    if(coins[j] <= i) {
      dp[i] = dp[i] < dp[i - coins[j]] + 1 ? dp[i] : dp[i - coins[j]] + 1;
    }
  }
}
printf("%d\n", dp[amount]);

medium

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Trace dp array updates for amount 6

   Calculate minimum coins for each amount: - dp[0]=0 - dp[1]=1 (1 coin) - dp[2]=2 (1+1) - dp[3]=1 (3 coin) - dp[4]=1 (4 coin) - dp[5]=2 (4+1) - dp[6]=2 (3+3)

2. Step 2: Final dp[6] value

   dp[6] = 2, minimum coins needed to make 6.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Minimum coins for 6 = 2 [OK]

Hint: Trace dp array from 0 to amount stepwise [OK]

Common Mistakes:

• Forgetting to update dp[i] with minimum value
• Incorrectly handling coin indices
• Assuming dp[i] equals i always

4. Identify the bug in this code snippet for Coin Change Minimum Coins:

int coins[] = {1, 2, 5};
int amount = 11;
int dp[12];
for(int i=0; i<=amount; i++) dp[i] = 0;
dp[0] = 0;
for(int i=1; i<=amount; i++) {
  for(int j=0; j<3; j++) {
    if(coins[j] <= i) {
      dp[i] = dp[i - coins[j]] + 1;
    }
  }
}
printf("%d\n", dp[amount]);

medium

A. dp array is not initialized with large values

B. dp[0] should be set to 1

C. The inner loop should run from j=1 to 3

D. The condition coins[j] <= i is incorrect

Solution

1. Step 1: Check dp initialization

   dp array is initialized with zeros, which incorrectly suggests zero coins needed for all amounts.

2. Step 2: Correct initialization needed

   dp should be initialized with a large number (like INT_MAX) to represent unreachable states, then updated with minimum coins.

3. Final Answer:

   dp array is not initialized with large values -> Option A

4. Quick Check:

   Initialize dp with max values to find minimum [OK]

Hint: Initialize dp with large values, not zeros [OK]

Common Mistakes:

• Setting dp to zero causes wrong minimum calculations
• Not updating dp[i] with minimum of previous values
• Incorrect loop ranges

5. Given coins = {2, 5, 10} and amount = 7, what is the minimum number of coins needed? If it is not possible, return -1. Use the Coin Change Minimum Coins logic.

hard

A. -1

B. 2

C. 3

D. 1

Solution

1. Step 1: Check possible combinations for amount 7

   Coins are 2, 5, 10. Possible sums: - 2+5=7 (2 coins) - 5+2=7 (2 coins) - 10 is too large So minimum coins = 2.

2. Step 2: Confirm no smaller combination

   Since 1-coin denominations are not available, 2 coins is minimum.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   7 = 2 + 5, minimum coins = 2 [OK]

Hint: Try all coin combos to find minimum or detect impossibility [OK]

Common Mistakes:

• Assuming 7 cannot be formed without 1-coin denomination
• Returning -1 incorrectly
• Ignoring order of coins