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 pocket. You try to use the fewest coins possible by checking all smaller amounts first and remembering the best way to make them.

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

We find min coins for each amount from 0 to 6:
0: 0 coins
1: min coins for 1
2: min coins for 2
...
6: min coins for 6

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 dp[0] = 0 and others as large number

dp = [0, ∞, ∞, ∞, ∞, ∞, ∞]

Why: 0 coins needed to make amount 0; others unknown yet

Step 2: Calculate dp[1]: check coins 1, 3, 4; only coin 1 fits

dp = [0, 1, ∞, ∞, ∞, ∞, ∞]

Why: 1 = 1 coin of 1

Step 3: Calculate dp[2]: check coins 1, 3, 4; only coin 1 fits

dp = [0, 1, 2, ∞, ∞, ∞, ∞]

Why: 2 = 2 coins of 1

Step 4: Calculate dp[3]: check coins 1, 3, 4; coin 3 fits with dp[0]

dp = [0, 1, 2, 1, ∞, ∞, ∞]

Why: 3 = 1 coin of 3 (better than 3 coins of 1)

Step 5: Calculate dp[4]: check coins 1, 3, 4; coin 4 fits with dp[0]

dp = [0, 1, 2, 1, 1, ∞, ∞]

Why: 4 = 1 coin of 4 (better than dp[3]+1=2)

Step 6: Calculate dp[5]: check coins 1, 3, 4; coin 1 fits with dp[4], coin 3 fits with dp[2], coin 4 fits with dp[1]

dp = [0, 1, 2, 1, 1, 2, ∞]

Why: 5 = min(dp[4]+1=2, dp[2]+1=3, dp[1]+1=2) = 2

Step 7: Calculate dp[6]: check coins 1, 3, 4; coin 1 fits with dp[5], coin 3 fits with dp[3], coin 4 fits with dp[2]

dp = [0, 1, 2, 1, 1, 2, 2]

Why: 6 = min(dp[5]+1=3, dp[3]+1=2, dp[2]+1=3) = 2

Result:

dp array: [0, 1, 2, 1, 1, 2, 2]
Minimum coins to make 6 = 2

Annotated Code

DSA C#

using System;

class CoinChange {
    public static int MinCoins(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            dp[i] = max; // initialize with large number
        }

        dp[0] = 0; // zero coins needed for amount 0

        for (int i = 1; i <= amount; i++) {
            foreach (int coin in coins) {
                if (coin <= i) {
                    dp[i] = Math.Min(dp[i], dp[i - coin] + 1); // update min coins
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }

    static void Main() {
        int[] coins = {1, 3, 4};
        int amount = 6;
        int result = MinCoins(coins, amount);
        Console.WriteLine(result);
    }
}

dp[i] = max; // initialize with large number

set initial dp values to large number to represent impossible amounts

dp[0] = 0; // zero coins needed for amount 0

base case: zero coins needed to make amount zero

foreach (int coin in coins) { if (coin <= i) { dp[i] = Math.Min(dp[i], dp[i - coin] + 1); // update min coins } }

for each amount i, try each coin to find minimum coins needed

return dp[amount] > amount ? -1 : dp[amount];

if dp[amount] is still large, no solution; else return min coins

Output

2

Complexity Analysis

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

Space: O(amount) because we store minimum coins needed for each amount up to target

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

Edge Cases

amount = 0

returns 0 since no coins are needed

DSA C#

dp[0] = 0; // zero coins needed for amount 0

coins array empty

returns -1 since no coins to use

DSA C#

return dp[amount] > amount ? -1 : dp[amount];

amount cannot be formed by given coins

returns -1 indicating no solution

DSA C#

return dp[amount] > amount ? -1 : dp[amount];

When to Use This Pattern

When asked for minimum coins or minimum steps to reach a target sum using given options, use dynamic programming to build solutions from smaller amounts up to the target.

Common Mistakes

Mistake: Not initializing dp array with a large number, causing incorrect minimum calculations
Fix: Initialize dp array elements with amount+1 or another large number to represent impossible states

Mistake: Not handling the base case dp[0] = 0
Fix: Explicitly set dp[0] = 0 because zero coins are needed to make amount zero

Mistake: Returning dp[amount] without checking if it is still large (no solution)
Fix: Check if dp[amount] > amount and return -1 if true to indicate no solution

Summary

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

Use when you need the fewest coins to form a specific amount from unlimited coin supply.

Build up the solution from smaller amounts using dynamic programming to avoid repeated work.

Practice

1. What does the "Coin Change Minimum Coins" problem ask you to find?
Given coins and an amount, find the minimum number of coins needed to make that amount.

easy

A. The smallest number of coins needed to make the amount

B. The total value of all coins

C. The maximum number of coins that can be used

D. The number of different coin types

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Clarify what is asked

   We want the smallest count of coins that sum exactly to the amount, not total value or max coins.

3. Final Answer:

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

4. Quick Check:

   Minimum coins = smallest count [OK]

Hint: Focus on minimum count, not total value or types [OK]

Common Mistakes:

• Confusing minimum coins with total coin value
• Thinking about maximum coins instead of minimum
• Counting coin types instead of coin quantity

2. Which of the following C# code snippets correctly initializes an array to store minimum coins for amounts 0 to 5, setting 0 coins for amount 0 and a large number for others?

easy

A. int[] minCoins = new int[5] {0, int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue};

B. int[] minCoins = new int[6] {0, int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue};

C. int[] minCoins = new int[6]; for(int i=1; i<=5; i++) minCoins[i] = 0;

D. int[] minCoins = new int[6]; minCoins[0] = int.MaxValue;

Solution

1. Step 1: Check array size and initialization

   We need an array of size 6 for amounts 0 to 5. Amount 0 requires 0 coins, others start with a large number.

2. Step 2: Verify each option

   int[] minCoins = new int[6] {0, int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue}; correctly initializes size 6 with 0 at index 0 and int.MaxValue for others. Others either have wrong size or wrong initialization.

3. Final Answer:

   int[] minCoins = new int[6] {0, int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue}; -> Option B

4. Quick Check:

   Array size 6, 0 at start, max values after [OK]

Hint: Array size = amount + 1, 0 coins for amount 0 [OK]

Common Mistakes:

• Using wrong array size
• Setting 0 coins for all amounts
• Setting int.MaxValue for amount 0

3. What is the output of the following C# code?

int[] coins = {1, 3, 4};
int amount = 6;
int[] minCoins = new int[amount + 1];
for (int i = 1; i <= amount; i++) minCoins[i] = int.MaxValue;

for (int i = 1; i <= amount; i++) {
    foreach (int coin in coins) {
        if (coin <= i && minCoins[i - coin] != int.MaxValue) {
            minCoins[i] = Math.Min(minCoins[i], minCoins[i - coin] + 1);
        }
    }
}
Console.WriteLine(minCoins[amount]);

medium

A. 3

B. int.MaxValue

C. 4

D. 2

Solution

1. Step 1: Initialize minCoins array

   minCoins[0] = 0 (default), others set to int.MaxValue initially.

2. Step 2: Calculate minCoins for amounts 1 to 6

   For amount 6, check coins 1,3,4:
   - Using coin 1: minCoins[5] + 1
   - Using coin 3: minCoins[3] + 1
   - Using coin 4: minCoins[2] + 1
   Calculations:
   minCoins[1] = 1 (coin 1)
   minCoins[2] = 2 (1+1)
   minCoins[3] = 1 (coin 3)
   minCoins[4] = 1 (coin 4)
   minCoins[5] = 2 (3+1 or 4+1)
   minCoins[6] = min(minCoins[5]+1, minCoins[3]+1, minCoins[2]+1) = min(3, 2, 3) = 2

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Minimum coins for 6 = 2 (3+3 or 4+1+1) [OK]

Hint: Trace minCoins array updates stepwise [OK]

Common Mistakes:

• Not updating minCoins correctly
• Ignoring int.MaxValue checks
• Miscounting coin combinations

4. Identify the error in this C# code snippet for minimum coin change and select the fix:

int[] coins = {1, 2, 5};
int amount = 11;
int[] minCoins = new int[amount + 1];
for (int i = 1; i <= amount; i++) minCoins[i] = int.MaxValue;

for (int i = 1; i <= amount; i++) {
    foreach (int coin in coins) {
        if (coin < i && minCoins[i - coin] != int.MaxValue) {
            minCoins[i] = Math.Min(minCoins[i], minCoins[i - coin] + 1);
        }
    }
}
Console.WriteLine(minCoins[amount]);

medium

A. Change loop to start from i = 0 instead of 1

B. Initialize minCoins array with zeros instead of int.MaxValue

C. Change 'coin < i' to 'coin <= i' in the if condition

D. Remove the if condition inside the foreach loop

Solution

1. Step 1: Analyze the if condition

   The condition 'coin < i' excludes cases where coin equals i, missing direct matches.

2. Step 2: Correct the condition

   Changing to 'coin <= i' allows using coins that exactly match the current amount, fixing the logic.

3. Final Answer:

   Change 'coin < i' to 'coin <= i' in the if condition -> Option C

4. Quick Check:

   Include coin equal to amount for correct min coins [OK]

Hint: Use <= to include exact coin matches [OK]

Common Mistakes:

• Using < instead of <= excludes valid coins
• Initializing minCoins incorrectly
• Removing necessary condition checks

5. You have coin denominations {2, 5, 10} and want to find the minimum coins for amount 7. Which approach correctly solves this using dynamic programming in C#?

hard

A. Initialize minCoins with 0 for amount 0 and int.MaxValue for others; update minCoins[i] by checking coins <= i and minCoins[i - coin] + 1

B. Initialize minCoins with zeros for all amounts; update minCoins[i] by adding 1 for each coin

C. Use recursion without memoization to find minimum coins

D. Initialize minCoins with int.MaxValue for all amounts including 0; update minCoins[i] by subtracting coin values

Solution

1. Step 1: Proper initialization

   Set minCoins[0] = 0 because zero coins are needed for amount 0; others set to int.MaxValue to represent unreachable amounts initially.

2. Step 2: Update minCoins using dynamic programming

   For each amount i, check each coin less than or equal to i. If minCoins[i - coin] is reachable, update minCoins[i] to the minimum of current value and minCoins[i - coin] + 1.

3. Final Answer:

   Initialize minCoins with 0 for amount 0 and int.MaxValue for others; update minCoins[i] by checking coins <= i and minCoins[i - coin] + 1 -> Option A

4. Quick Check:

   DP with correct initialization and update finds minimum coins [OK]

Hint: Initialize 0 for amount 0, update with min of previous +1 [OK]

Common Mistakes:

• Initializing all minCoins to zero
• Using recursion without memoization causing inefficiency
• Incorrectly updating minCoins by subtraction