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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of minimum coins for amount 11

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

DSA Java

public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            dp[i] = amount + 1;
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(minCoins(coins, amount));
    }
}

A 3

B -1

C 5

D 4

💡 Hint

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

The minimum coins to make 11 are 5 + 5 + 1 = 3 coins.

❓ Predict Output

intermediate

Output when no solution exists

What is the output of the code when coins are {2, 4} and amount is 7?

DSA Java

public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            dp[i] = amount + 1;
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {2, 4};
        int amount = 7;
        System.out.println(minCoins(coins, amount));
    }
}

A 3

B 2

C 1

D -1

💡 Hint

Check if 7 can be formed by any combination of 2 and 4.

7 cannot be formed by any combination of 2 and 4, so output is -1.

🔧 Debug

advanced

Identify the error in coin change code

What error does the following code produce when run?

DSA Java

public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        int[] dp = new int[amount];
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = amount + 1;
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(minCoins(coins, amount));
    }
}

A ArrayIndexOutOfBoundsException

B No error, outputs 3

C NullPointerException

D Compilation error

💡 Hint

Check the size of dp array and its indexing.

dp array size is amount, but code accesses dp[amount], causing ArrayIndexOutOfBoundsException.

🧠 Conceptual

advanced

Why use dynamic programming for coin change?

Why is dynamic programming a good approach to solve the minimum coin change problem?

A Because it sorts coins and picks the largest first always

B Because it randomly picks coins until amount is reached

C Because it solves subproblems once and reuses results to avoid repeated work

D Because it uses recursion without storing intermediate results

💡 Hint

Think about overlapping subproblems and optimal substructure.

Dynamic programming stores results of smaller amounts to build up solution for larger amounts efficiently.

🚀 Application

expert

Minimum coins for large amount with given coins

Given coins {1, 3, 4} and amount 6, what is the minimum number of coins needed?

A 3

B 2

C 1

D 4

💡 Hint

Try combinations like 3+3 or 4+1+1.

Minimum coins for 6 are 3 + 3 = 2 coins.

Practice

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

easy

A. Minimum number of coins needed to make the amount

B. Maximum number of coins needed to make the amount

C. Number of ways to make the amount

D. Sum of all coin denominations

Solution

1. Step 1: Understand the problem statement

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

2. Step 2: Differentiate from similar problems

   It is not about counting ways or maximum coins, but the minimum coins required.

3. Final Answer:

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

4. Quick Check:

   Minimum coins = minimum coins needed [OK]

Hint: Focus on 'minimum coins' needed, not ways or sums [OK]

Common Mistakes:

• Confusing minimum coins with number of ways
• Thinking about maximum coins instead of minimum
• Ignoring the total amount requirement

2. Which of the following Java method signatures correctly represents a function to find minimum coins for a given amount?

public static int minCoins(int[] coins, int amount)

easy

A. public int minCoins(int coins, int[] amount)

B. public static int minCoins(int[] coins, int amount)

C. static void minCoins(int[] coins, int amount)

D. public static int minCoins(int amount, int[] coins)

Solution

1. Step 1: Check parameter types and order

   The method should accept an array of coin denominations and an integer amount, in that order.

2. Step 2: Check return type and modifiers

   It should return an int representing minimum coins and be static for utility use.

3. Final Answer:

   public static int minCoins(int[] coins, int amount) -> Option B

4. Quick Check:

   Correct signature = public static int minCoins(int[] coins, int amount) [OK]

Hint: Array first, amount second; return int minimum coins [OK]

Common Mistakes:

• Swapping parameter order
• Wrong return type (void instead of int)
• Missing static keyword if utility method

3. What is the output of the following Java code?

public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        java.util.Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 3, 4};
        int amount = 6;
        System.out.println(minCoins(coins, amount));
    }
}

medium

A. -1

B. 3

C. 1

D. 2

Solution

1. Step 1: Understand the DP array filling

   dp[i] stores minimum coins for amount i. Initialized with max (7 here) except dp[0]=0.

2. Step 2: Calculate dp values for amount=6

   Using coins {1,3,4}: - dp[1] = 1 (1 coin of 1) - dp[2] = 2 (1+1) - dp[3] = 1 (coin 3) - dp[4] = 1 (coin 4) - dp[5] = 2 (4+1) - dp[6] = min(dp[6-1]+1=dp[5]+1=3, dp[6-3]+1=dp[3]+1=2, dp[6-4]+1=dp[2]+1=3) = 2

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Minimum coins for 6 = 2 [OK]

Hint: Trace dp array updates for each amount [OK]

Common Mistakes:

• Not initializing dp array correctly
• Returning dp[amount] without checking if solution exists
• Confusing dp indices or coin subtraction

4. Find the error in the following Java code snippet for minimum coin change:

public static int minCoins(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

medium

A. Using Integer.MAX_VALUE causes overflow when adding 1

B. dp array size should be amount, not amount + 1

C. dp[0] should be Integer.MAX_VALUE, not 0

D. The for loop should start from 0, not 1

Solution

1. Step 1: Identify the problem with Integer.MAX_VALUE

   Adding 1 to Integer.MAX_VALUE causes integer overflow, leading to incorrect dp values.

2. Step 2: Explain correct initialization

   Use a large number less than Integer.MAX_VALUE (like amount+1) to avoid overflow when adding 1.

3. Final Answer:

   Using Integer.MAX_VALUE causes overflow when adding 1 -> Option A

4. Quick Check:

   Integer.MAX_VALUE + 1 overflows [OK]

Hint: Avoid Integer.MAX_VALUE for dp initialization to prevent overflow [OK]

Common Mistakes:

• Ignoring overflow when adding 1 to max value
• Wrong dp array size
• Incorrect dp[0] initialization

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

medium

A. 1

B. 3

C. 2

D. -1

Solution

1. Step 1: Check possible combinations for amount 7

   Coins: 2, 5, 10 - 2+5=7 (2 coins) - 5+2=7 (2 coins) - 10 is too big But 2+5=7 is valid, so minimum coins = 2.

2. Step 2: Verify if amount 7 can be formed

   Actually, 2+5=7 is valid, so minimum coins = 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   7 = 5 + 2 = 2 coins [OK]

Hint: Try largest coin first, then smaller coins [OK]

Common Mistakes:

• Assuming no solution without checking combinations
• Ignoring order of coins
• Returning -1 prematurely