Coin Change Minimum Coins in DSA C - Time & Space Complexity

Time Complexity: Coin Change Minimum Coins

O(amount * n)

Understanding Time Complexity

We want to know how the time needed to find the minimum coins changes as the amount grows.

How does the number of coins and the amount affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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) {
                dp[i] = dp[i] < dp[i - coins[j]] + 1 ? dp[i] : dp[i - coins[j]] + 1;
            }
        }
    }
    return dp[amount];
}
    

This code finds the minimum number of coins needed to make the given amount using the coin denominations.

Identify Repeating Operations

Look at the loops that repeat work:

• Primary operation: The inner loop checks all coin types for each amount value.
• How many times: The outer loop runs once for each amount from 1 to amount (amount times), and the inner loop runs for each coin type (n times).

How Execution Grows With Input

As the amount grows, the work grows by checking all coins for each amount value.

Input Size (amount)	Approx. Operations
10	10 * number_of_coins
100	100 * number_of_coins
1000	1000 * number_of_coins

Pattern observation: The operations grow roughly in a straight line with the amount, multiplied by the number of coin types.

Final Time Complexity

Time Complexity: O(amount * n)

This means the time grows proportionally to the amount times the number of coin types.

Common Mistake

[X] Wrong: "The time depends only on the amount, not the number of coins."

[OK] Correct: Each coin type is checked for every amount, so more coin types mean more work.

Interview Connect

Understanding this helps you explain how dynamic programming solves problems efficiently by breaking them into smaller parts.

Self-Check

"What if we used recursion without memoization? How would the time complexity change?"

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