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++

int coins[] = {1, 2, 5};
int amount = 11;
int n = sizeof(coins)/sizeof(coins[0]);
int dp[12];
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
    dp[i] = amount + 1;
    for (int j = 0; j < n; j++) {
        if (coins[j] <= i) {
            dp[i] = std::min(dp[i], dp[i - coins[j]] + 1);
        }
    }
}
std::cout << dp[amount] << std::endl;

A 4

B 3

C 5

D 2

💡 Hint

Think about the fewest coins that add up 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 base case in Coin Change DP

In the coin change minimum coins dynamic programming solution, what is the purpose of setting dp[0] = 0?

A It means zero coins are needed to make amount zero.

B It initializes the array to zero for all amounts.

C It indicates no solution exists for amount zero.

D It sets the maximum number of coins for amount zero.

💡 Hint

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

dp[0] = 0 means no coins are needed to make amount zero, which is the base case for building solutions.

🔧 Debug

advanced

Identify the error in this Coin Change code snippet

What error will this C++ code produce when trying to find minimum coins for amount 7 with coins {2, 4}? int coins[] = {2, 4}; int amount = 7; int n = sizeof(coins)/sizeof(coins[0]); int dp[8]; dp[0] = 0; for (int i = 1; i <= amount; i++) { dp[i] = amount + 1; for (int j = 0; j < n; j++) { if (coins[j] <= i) { dp[i] = std::min(dp[i], dp[i - coins[j]] + 1); } } } std::cout << dp[amount] << std::endl;

A It outputs 3

B It outputs 2

C It outputs 8

D It outputs 2147483648

💡 Hint

Check if amount 7 can be formed by coins 2 and 4.

Amount 7 cannot be formed by coins 2 and 4, so dp[7] remains amount+1 (8), indicating no solution.

🚀 Application

advanced

Minimum coins for amount 0 with any coin set

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

A Amount of coins in the set

B 1

C -1

D 0

💡 Hint

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

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

❓ Predict Output

expert

Output of minimum coins for amount 10 with coins {3, 7}

What is the output of the following C++ code that calculates the minimum number of coins needed to make amount 10 using coins {3, 7}? int coins[] = {3, 7}; int amount = 10; int n = sizeof(coins)/sizeof(coins[0]); int dp[11]; dp[0] = 0; for (int i = 1; i <= amount; i++) { dp[i] = amount + 1; for (int j = 0; j < n; j++) { if (coins[j] <= i) { dp[i] = std::min(dp[i], dp[i - coins[j]] + 1); } } } if (dp[amount] > amount) std::cout << -1 << std::endl; else std::cout << dp[amount] << std::endl;

A 2

B 3

C -1

D 1

💡 Hint

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

Amount 10 can be formed by 7 + 3, which is 2 coins, so output is 2.

Practice

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

easy

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

B. The total number of different coins available

C. The maximum amount of money you can make with given coins

D. The 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 fewest number of coins needed to make a given amount correctly describes this goal, while others describe unrelated concepts.

3. Final Answer:

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

4. Quick Check:

   Minimum coins = fewest coins needed [OK]

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

Common Mistakes:

• Confusing minimum coins with total coin types
• Thinking about maximum amount instead of minimum coins
• Mixing sum of coins with count of coins

2. Which of the following is the correct C++ syntax to declare a vector named dp of size amount+1 initialized with INT_MAX?

easy

A. vector<int> dp(amount, 0);

B. std::vector dp(amount+1, INT_MAX);

C. std::vector<int> dp(amount+1, INT_MAX);

D. vector<int> dp = new vector(amount+1, INT_MAX);

Solution

1. Step 1: Check vector declaration syntax

   Correct syntax uses std::vector<int> dp(size, initial_value); std::vector<int> dp(amount+1, INT_MAX); matches this exactly.

2. Step 2: Identify errors in other options

   vector<int> dp(amount, 0); initializes with 0 and wrong size; std::vector dp(amount+1, INT_MAX); misses template brackets; vector<int> dp = new vector(amount+1, INT_MAX); uses incorrect new syntax.

3. Final Answer:

   std::vector<int> dp(amount+1, INT_MAX); -> Option C

4. Quick Check:

   Correct vector declaration = std::vector<int> dp(amount+1, INT_MAX); [OK]

Hint: Use std::vector<Type> name(size, value) for initialization [OK]

Common Mistakes:

• Omitting template brackets <>
• Using wrong initialization syntax
• Confusing size and initial value parameters

3. What is the output of the following C++ code snippet?

int coins[] = {1, 2, 5};
int amount = 11;
std::vector<int> dp(amount+1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
  for (int c : coins) {
    if (i - c >= 0 && dp[i - c] != INT_MAX) {
      dp[i] = std::min(dp[i], dp[i - c] + 1);
    }
  }
}
std::cout << dp[amount] << std::endl;

medium

A. 11

B. 3

C. 5

D. INT_MAX

Solution

1. Step 1: Understand the DP approach

   The code finds minimum coins to make amount 11 using coins {1,2,5} by building dp array.

2. Step 2: Calculate minimum coins for 11

   11 = 5 + 5 + 1 uses 3 coins, which is minimum. dp[11] = 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Minimum coins for 11 = 3 [OK]

Hint: Try largest coins first to minimize count [OK]

Common Mistakes:

• Assuming dp[amount] remains INT_MAX
• Counting total coin value instead of count
• Ignoring dp initialization and updates

4. Identify the error in this C++ code snippet for Coin Change Minimum Coins:

int coins[] = {1, 3, 4};
int amount = 6;
std::vector<int> dp(amount+1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
  for (int c : coins) {
    if (i - c >= 0) {
      dp[i] = std::min(dp[i], dp[i - c] + 1);
    }
  }
}
std::cout << dp[amount] << std::endl;

medium

A. dp[0] should be initialized to INT_MAX

B. Wrong initialization of dp vector size

C. Incorrect coin denominations array syntax

D. Missing check if dp[i - c] is INT_MAX before adding 1

Solution

1. Step 1: Analyze dp update condition

   The code updates dp[i] without checking if dp[i - c] is INT_MAX, which can cause overflow.

2. Step 2: Identify missing condition

   Must check dp[i - c] != INT_MAX before adding 1 to avoid invalid calculations.

3. Final Answer:

   Missing check if dp[i - c] is INT_MAX before adding 1 -> Option D

4. Quick Check:

   Check dp[i - c] != INT_MAX before update [OK]

Hint: Always check dp[i-c] != INT_MAX before adding 1 [OK]

Common Mistakes:

• Skipping dp[i-c] validity check
• Incorrect dp vector size
• Wrong initialization of dp[0]

5. Given coin denominations {2, 5, 10} and amount 7, what is the minimum number of coins needed? If it is not possible, return -1.

hard

A. 2

B. 3

C. -1

D. 1

Solution

1. Step 1: Check possible combinations for amount 7

   Coins are 2, 5, 10. 10 > 7 so ignore. Try 5 + 2 = 7 (2 coins). But 5 + 2 is valid, so minimum coins = 2.

2. Step 2: Verify if 5 + 2 is allowed

   Since 5 and 2 are in denominations, 7 can be made with 2 coins.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   7 = 5 + 2 uses 2 coins [OK]

Hint: Try combinations starting from largest coin [OK]

Common Mistakes:

• Assuming no solution because 7 is odd
• Ignoring valid combinations with smaller coins
• Returning -1 incorrectly