Rod Cutting Problem in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Rod Cutting

What is the output of the following Java code that uses a simple recursive approach to solve the rod cutting problem for a rod of length 4?

DSA Java

public class RodCutting {
    static int cutRod(int[] price, int n) {
        if (n <= 0) return 0;
        int max_val = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            max_val = Math.max(max_val, price[i - 1] + cutRod(price, n - i));
        }
        return max_val;
    }
    public static void main(String[] args) {
        int[] price = {1, 5, 8, 9};
        int length = 4;
        System.out.println(cutRod(price, length));
    }
}

A 10

B 5

C 8

D 9

💡 Hint

Consider all possible cuts and sum their prices recursively.

The maximum revenue for length 4 is obtained by cutting into lengths 2 and 2, each priced 5, total 10.

❓ Predict Output

intermediate

Output of Bottom-Up DP Rod Cutting

What is the output of this Java code using bottom-up dynamic programming for rod cutting with prices {2, 5, 7, 8} and rod length 4?

DSA Java

public class RodCuttingDP {
    static int cutRod(int[] price, int n) {
        int[] val = new int[n + 1];
        val[0] = 0;
        for (int i = 1; i <= n; i++) {
            int max_val = Integer.MIN_VALUE;
            for (int j = 1; j <= i; j++) {
                max_val = Math.max(max_val, price[j - 1] + val[i - j]);
            }
            val[i] = max_val;
        }
        return val[n];
    }
    public static void main(String[] args) {
        int[] price = {2, 5, 7, 8};
        int length = 4;
        System.out.println(cutRod(price, length));
    }
}

A 7

B 9

C 8

D 10

💡 Hint

Use the DP array to build solutions from smaller lengths.

The best cut is length 2 + length 2, prices 5 + 5 = 10.

🔧 Debug

advanced

Identify the Error in Memoized Rod Cutting

What error does this Java code produce when running the memoized rod cutting function?

DSA Java

public class RodCuttingMemo {
    static int cutRodMemo(int[] price, int n, int[] memo) {
        if (n <= 0) return 0;
        if (memo[n] >= 0) return memo[n];
        int max_val = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            max_val = Math.max(max_val, price[i - 1] + cutRodMemo(price, n - i, memo));
        }
        memo[n] = max_val;
        return max_val;
    }
    public static void main(String[] args) {
        int[] price = {1, 5, 8, 9};
        int length = 4;
        int[] memo = new int[length + 1];
        for (int i = 0; i <= length; i++) memo[i] = -1;
        System.out.println(cutRodMemo(price, length, memo));
    }
}

A NullPointerException

B ArrayIndexOutOfBoundsException

C Prints 10 correctly

D StackOverflowError

💡 Hint

Check the size of the memo array and the indices used.

Memo array size is length 4 but accessed at index 4 causing out of bounds.

🧠 Conceptual

advanced

Time Complexity of Rod Cutting Algorithms

What is the time complexity of the bottom-up dynamic programming solution for the rod cutting problem with rod length n?

A O(n^2)

B O(n)

C O(2^n)

D O(n log n)

💡 Hint

Consider the nested loops in the DP solution.

The outer loop runs n times and inner loop runs up to n times, total O(n^2).

🚀 Application

expert

Maximum Revenue and Cuts for Rod Length 5

Given prices {2, 5, 7, 8, 10} for rod lengths 1 to 5, what is the maximum revenue and the cuts that produce it for rod length 5 using bottom-up DP?

A Revenue: 11, Cuts: 1 + 4

B Revenue: 10, Cuts: 5

C Revenue: 12, Cuts: 2 + 3

D Revenue: 13, Cuts: 1 + 1 + 3

💡 Hint

Try all cut combinations and sum their prices.

Cutting into lengths 2 and 3 yields 5 + 7 = 12, which is maximum.

Practice

1. What is the main goal of the Rod Cutting Problem in algorithms?

easy

A. To find the shortest rod length possible

B. To maximize the total profit by cutting the rod into pieces

C. To minimize the number of cuts made on the rod

D. To count the total number of ways to cut the rod

Solution

1. Step 1: Understand the problem objective

   The rod cutting problem aims to cut a rod into pieces to get the highest total price from selling those pieces.

2. Step 2: Identify the optimization goal

   The goal is to maximize profit, not minimize cuts or count ways.

3. Final Answer:

   To maximize the total profit by cutting the rod into pieces -> Option B

4. Quick Check:

   Maximize profit = To maximize the total profit by cutting the rod into pieces [OK]

Hint: Focus on maximizing profit, not minimizing cuts [OK]

Common Mistakes:

• Thinking the goal is to minimize cuts
• Confusing with counting ways to cut
• Assuming shortest rod length is the goal

2. Which of the following is the correct way to declare the price array for rod lengths in Java?

easy

A. int[] price = {1, 5, 8, 9};

B. int price[] = (1, 5, 8, 9);

C. int price = {1, 5, 8, 9};

D. int[] price = (1, 5, 8, 9);

Solution

1. Step 1: Recall Java array declaration syntax

   In Java, arrays are declared with square brackets and initialized with curly braces.

2. Step 2: Check each option

   int[] price = {1, 5, 8, 9}; uses correct syntax: int[] price = {1, 5, 8, 9};. Others use parentheses or wrong assignment.

3. Final Answer:

   int[] price = {1, 5, 8, 9}; -> Option A

4. Quick Check:

   Correct Java array syntax = int[] price = {1, 5, 8, 9}; [OK]

Hint: Use curly braces {} to initialize arrays in Java [OK]

Common Mistakes:

• Using parentheses () instead of curly braces {}
• Missing square brackets [] in declaration
• Assigning array to int variable

3. What will be the output of the following Java code snippet for rod length 4?

int[] price = {1, 5, 8, 9};
int n = 4;
int maxVal = 0;
for (int i = 1; i <= n; i++) {
    maxVal = Math.max(maxVal, price[i-1] + price[n - i]);
}
System.out.println(maxVal);

medium

A. 13

B. 9

C. 10

D. 8

Solution

1. Step 1: Trace the loop iterations and calculations

   For n=4, loop i=1 to 4:
   i=1: maxVal = max(0, price[0]+price[3]) = max(0,1+9)=10
   i=2: maxVal = max(10, price[1]+price[2])=max(10,5+8)=13
   i=3: maxVal = max(13, price[2]+price[1])=max(13,8+5)=13
   i=4: maxVal = max(13, price[3]+price[0])=max(13,9+1)=13

2. Step 2: Identify the final maxVal value

   After loop, maxVal is 13, but code prints maxVal after loop ends. The code prints 13.

3. Final Answer:

   13 -> Option A

4. Quick Check:

   Max profit for length 4 = 13 [OK]

Hint: Check all splits and sum prices to find max [OK]

Common Mistakes:

• Not considering all splits i=1 to n
• Off-by-one errors in array indexing
• Printing maxVal before loop ends

4. Identify the error in this Java method for rod cutting:

public int cutRod(int[] price, int n) {
    if (n <= 0) return 0;
    int maxVal = Integer.MIN_VALUE;
    for (int i = 1; i < n; i++) {
        maxVal = Math.max(maxVal, price[i-1] + cutRod(price, n - i));
    }
    return maxVal;
}

medium

A. Recursive call parameters are incorrect

B. Base case should return 1 instead of 0

C. Loop should run from i = 1 to i <= n

D. maxVal should be initialized to 0 instead of Integer.MIN_VALUE

Solution

1. Step 1: Analyze the loop range

   The loop runs from i=1 to i<n, so it misses the case i=n which is needed to consider the whole rod as one piece.

2. Step 2: Correct the loop condition

   The loop should run from i=1 to i<=n to include all possible cuts including the full length.

3. Final Answer:

   Loop should run from i = 1 to i <= n -> Option C

4. Quick Check:

   Include full length cut by looping to i <= n [OK]

Hint: Loop must include full rod length i = n [OK]

Common Mistakes:

• Using i < n instead of i <= n
• Incorrect base case return value
• Wrong initialization of maxVal

5. Given a rod of length 5 and price array int[] price = {2, 5, 7, 8, 10};, what is the maximum profit using dynamic programming approach?

hard

A. 14

B. 10

C. 15

D. 12

Solution

1. Step 1: Calculate max profit for each length up to 5

   Length 1: max = 2
   Length 2: max = max(5, 2+2=4) = 5
   Length 3: max = max(7, 5+2=7, 2+5=7) = 7
   Length 4: max = max(8, 7+2=9, 5+5=10, 2+7=9) = 10
   Length 5: max = max(10, 10+2=12, 7+5=12, 5+7=12, 2+10=12) = 12

2. Step 2: Check if cutting into smaller pieces yields better profit

   Try cutting length 5 into 1+4, 2+3, 3+2, 4+1 etc. The best is 2+3 or 3+2 or 1+4 giving 12, but also check if full length price 10 is less than these.

3. Step 3: Recalculate carefully

   Check all splits:
   1+4: 2 + 10 = 12
   2+3: 5 + 7 = 12
   3+2: 7 + 5 = 12
   4+1: 8 + 2 = 10
   But also check if cutting into 1+1+3 or 1+1+1+2 etc. can yield more.
   Try 1+1+3: 2+2+7=11
   Try 1+1+1+2: 2+2+2+5=11
   Try 1+1+1+1+1: 2*5=10
   So max is 12.

4. Final Answer:

   12 -> Option D

5. Quick Check:

   Max profit for length 5 = 12 [OK]

Hint: Check all splits and pick max sum for length 5 [OK]

Common Mistakes:

• Choosing price of full length only
• Not checking all split combinations
• Confusing price array indices