Coin Change Minimum Coins in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of minimum coins for amount 11

What is the output of the following C code that calculates the minimum number of coins needed to make amount 11 using coins {1, 2, 5}?

DSA C

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

int minCoins(int coins[], int n, int amount) {
    int dp[amount+1];
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        dp[i] = INT_MAX;
        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;
            }
        }
    }
    return dp[amount];
}

int main() {
    int coins[] = {1, 2, 5};
    int amount = 11;
    int n = sizeof(coins)/sizeof(coins[0]);
    int result = minCoins(coins, n, amount);
    printf("%d\n", result);
    return 0;
}

A 3

B 4

C 5

D 2

💡 Hint

Think about the fewest coins that sum to 11 using 1, 2, and 5.

The minimum coins to make 11 are 5 + 5 + 1, which is 3 coins.

🧠 Conceptual

intermediate

Understanding the DP array in Coin Change

In the coin change minimum coins problem, what does the dp array represent after the algorithm finishes?

A dp[i] stores the coin denomination used last to make amount i

B dp[i] stores the maximum number of coins needed to make amount i

C dp[i] stores the total number of ways to make amount i

D dp[i] stores the minimum number of coins needed to make amount i

💡 Hint

Think about what the algorithm tries to minimize for each amount.

The dp array holds the minimum coins needed for every amount from 0 up to the target amount.

🔧 Debug

advanced

Identify the error causing wrong output

The following code tries to find the minimum coins for amount 7 using coins {2, 3, 6}, but it outputs 2147483647. What is the cause?

DSA C

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

int minCoins(int coins[], int n, int amount) {
    int dp[amount+1];
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        dp[i] = INT_MAX;
        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;
            }
        }
    }
    return dp[amount];
}

int main() {
    int coins[] = {2, 3, 6};
    int amount = 7;
    int n = sizeof(coins)/sizeof(coins[0]);
    int result = minCoins(coins, n, amount);
    printf("%d\n", result);
    return 0;
}

A The coins array is missing the coin 1

B The condition should be coins[j] <= i instead of coins[j] < i

C The return statement should return dp[amount-1]

D dp array is not initialized for dp[0]

💡 Hint

Check the condition that decides if a coin can be used for amount i.

The condition coins[j] < i excludes the case when coins[j] == i, so dp[i] never updates for exact coin matches, causing dp[i] to remain INT_MAX.

🚀 Application

advanced

Minimum coins for amount 0

What is the minimum number of coins needed to make amount 0 using any set of coins?

A -1

B 1

C 0

D Undefined

💡 Hint

Think about how many coins you need to make zero amount.

No coins are needed to make amount 0, so the answer is 0.

❓ Predict Output

expert

Output of minimum coins with no solution

What is the output of the following code when trying to make amount 7 with coins {5, 10}?

DSA C

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

int minCoins(int coins[], int n, int amount) {
    int dp[amount+1];
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        dp[i] = INT_MAX;
        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;
            }
        }
    }
    if (dp[amount] == INT_MAX) return -1;
    return dp[amount];
}

int main() {
    int coins[] = {5, 10};
    int amount = 7;
    int n = sizeof(coins)/sizeof(coins[0]);
    int result = minCoins(coins, n, amount);
    printf("%d\n", result);
    return 0;
}

A -1

B 2

C 1

D 0

💡 Hint

Check if amount 7 can be formed by coins 5 and 10.

Amount 7 cannot be formed by any combination of 5 and 10 coins, so the function returns -1.

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