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.