Greedy vs DP How to Know Which to Apply in DSA Java - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Greedy Coin Change Algorithm

What is the output of the following Java code that uses a greedy approach to make change for 30 cents with coins 25, 10, 5, and 1?

DSA Java

int[] coins = {25, 10, 5, 1};
int amount = 30;
int count = 0;
for (int coin : coins) {
    count += amount / coin;
    amount %= coin;
}
System.out.println(count);

A 2

B 3

C 4

D 5

💡 Hint

Think about how many coins of each type the greedy method picks.

The greedy method picks one 25-cent coin and one 5-cent coin, totaling 2 coins. But since 30 = 25 + 5, the count is 2. However, the code counts coins by dividing and summing: 30/25=1 coin, remainder 5; 5/10=0 coin; 5/5=1 coin; total 2 coins.

🧠 Conceptual

intermediate

Choosing Between Greedy and Dynamic Programming

Which of the following statements best explains when to use a greedy algorithm instead of dynamic programming?

A Use greedy when the problem has no subproblems and no optimal substructure.

B Use greedy when the problem has overlapping subproblems but no optimal substructure.

C Use greedy when the problem has optimal substructure and the greedy choice property.

D Use greedy when the problem requires checking all possible combinations.

💡 Hint

Greedy algorithms work when making local optimal choices leads to a global optimum.

Greedy algorithms work when the problem has optimal substructure and the greedy choice property, meaning local choices lead to a global optimum without needing to explore all subproblems.

🔧 Debug

advanced

Why Does This Greedy Algorithm Fail for Coin Change?

The following Java code tries to find the minimum number of coins for 6 cents using coins 1, 3, and 4. Why does it fail to find the minimum number of coins?

DSA Java

int[] coins = {4, 3, 1};
int amount = 6;
int count = 0;
for (int coin : coins) {
    count += amount / coin;
    amount %= coin;
}
System.out.println(count);

A It fails because the greedy approach does not consider all combinations and misses the optimal solution.

B It fails because the coins array is not sorted in ascending order.

C It fails because the code uses integer division instead of floating-point division.

D It fails because the amount variable is not updated inside the loop.

💡 Hint

Think about whether greedy always works for all coin sets.

The greedy approach fails here because it picks one 4-cent coin and then two 1-cent coins (total 3 coins), but the optimal solution is two 3-cent coins (2 coins). Greedy does not explore all combinations.

❓ Predict Output

advanced

Dynamic Programming Output for Coin Change

What is the output of this Java code that uses dynamic programming to find the minimum number of coins for 6 cents with coins 1, 3, and 4?

DSA Java

int[] coins = {1, 3, 4};
int amount = 6;
int[] dp = new int[amount + 1];
java.util.Arrays.fill(dp, amount + 1);
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);
        }
    }
}
System.out.println(dp[amount]);

A 1

B 3

C 4

D 2

💡 Hint

Check how dp array builds up minimum coins for each amount.

The dp array finds the minimum coins for 6 cents as 2 (two 3-cent coins). The code correctly computes dp[6] = 2.

🧠 Conceptual

expert

Identifying Optimal Substructure and Greedy Choice Property

Which problem below has both optimal substructure and the greedy choice property, making it suitable for a greedy algorithm?

A Scheduling tasks to maximize the number of non-overlapping intervals.

B Finding the shortest path in a graph with negative edge weights.

C Finding the longest increasing subsequence in an array.

D Partitioning a set into two subsets with equal sum.

💡 Hint

Greedy works well when local choices lead to global optimum without backtracking.

Scheduling tasks to maximize non-overlapping intervals has optimal substructure and greedy choice property, so greedy algorithms work well. Other problems require dynamic programming or have no greedy property.

Practice

1. Which of the following best describes when to use a greedy algorithm instead of dynamic programming?

easy

A. When the problem needs to store all intermediate results

B. When the problem requires checking all possible combinations

C. When the problem has overlapping subproblems but no optimal substructure

D. When the problem has the greedy choice property and optimal substructure

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm works when choosing the best option at each step leads to a global optimum.

2. Step 2: Recognize optimal substructure

   Optimal substructure means the optimal solution can be built from optimal solutions of subproblems.

3. Final Answer:

   When the problem has the greedy choice property and optimal substructure -> Option D

4. Quick Check:

   Greedy = greedy choice + optimal substructure [OK]

Hint: Use greedy if local best leads to global best [OK]

Common Mistakes:

• Confusing overlapping subproblems with greedy applicability
• Using greedy when problem needs full exploration
• Ignoring optimal substructure requirement

2. Which Java syntax correctly declares a 2D array for dynamic programming table initialization?

easy

A. int[][] dp = new int[5];

B. int dp[][] = new int(5,5);

C. int[][] dp = new int[5][5];

D. int dp[5][5] = new int[][];

Solution

1. Step 1: Recall Java 2D array syntax

   Java uses new int[rows][columns] to declare 2D arrays.

2. Step 2: Check each option

   int[][] dp = new int[5][5]; uses correct syntax. Options A, B, C have syntax errors or incomplete declarations.

3. Final Answer:

   int[][] dp = new int[5][5]; -> Option C

4. Quick Check:

   Correct 2D array declaration = int[][] dp = new int[5][5]; [OK]

Hint: Use new int[rows][cols] for 2D arrays in Java [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Missing size in second dimension
• Incorrect array initialization syntax

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

int[] coins = {1, 2, 5};
int amount = 11;
int count = 0;
for (int i = coins.length - 1; i >= 0; i--) {
    count += amount / coins[i];
    amount %= coins[i];
}
System.out.println(count);

medium

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Trace the loop from largest coin to smallest

   Start with amount=11, coins = [1,2,5]. i=2 (coin=5): count += 11/5=2, amount=11%5=1.

2. Step 2: Continue with next coins

   i=1 (coin=2): count += 1/2=0, amount=1%2=1; i=0 (coin=1): count += 1/1=1, amount=1%1=0.

3. Step 3: Calculate total count

   Total count = 2 + 0 + 1 = 3.

4. Final Answer:

   3 -> Option A

5. Quick Check:

   Greedy coin count = 3 [OK]

Hint: Divide and mod with largest coin first [OK]

Common Mistakes:

• Adding counts incorrectly
• Mixing up division and modulo
• Ignoring order of coins

4. The following code attempts to solve the coin change problem using greedy approach. What is the bug?

int[] coins = {1, 3, 4};
int amount = 6;
int count = 0;
for (int i = coins.length - 1; i >= 0; i--) {
    count += amount / coins[i];
    amount %= coins[i];
}
System.out.println(count);

medium

A. Division by zero error

B. Greedy fails because coin set lacks greedy choice property

C. Array index out of bounds error

D. Incorrect initialization of count variable

Solution

1. Step 1: Understand greedy choice property failure

   Coins {1,3,4} do not guarantee greedy choice property for amount 6.

2. Step 2: Trace greedy approach output

   Greedy picks 4 once (count=1), remainder 2; then picks two 1s (count=3). But optimal is two 3s (count=2).

3. Final Answer:

   Greedy fails because coin set lacks greedy choice property -> Option B

4. Quick Check:

   Greedy fails if no greedy choice property [OK]

Hint: Check if greedy choice property holds before using greedy [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Ignoring optimal substructure requirement
• Confusing runtime errors with logic errors

5. Given a set of tasks with start and end times, which approach is best to find the maximum number of non-overlapping tasks?

class Task {
    int start, end;
    Task(int s, int e) { start = s; end = e; }
}

Choose the correct approach and why.

hard

A. Use greedy by sorting tasks by earliest finish time to select tasks

B. Use dynamic programming to check all subsets of tasks

C. Use greedy by sorting tasks by longest duration first

D. Use dynamic programming to store maximum tasks ending at each time

Solution

1. Step 1: Identify problem type

   This is the activity selection problem, classic greedy example.

2. Step 2: Choose greedy approach

   Sorting by earliest finish time ensures maximum tasks without overlap.

3. Step 3: Compare options

   Use greedy by sorting tasks by earliest finish time to select tasks matches known greedy solution; DP is possible but less efficient here.

4. Final Answer:

   Use greedy by sorting tasks by earliest finish time to select tasks -> Option A

5. Quick Check:

   Activity selection = greedy by finish time [OK]

Hint: Sort tasks by finish time for max non-overlapping tasks [OK]

Common Mistakes:

• Sorting by start time or duration instead of finish time
• Using DP unnecessarily increasing complexity
• Ignoring greedy choice property in scheduling