Rod Cutting Problem in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Rod Cutting

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

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int cutRod(const vector<int>& price, int n) {
    if (n <= 0) return 0;
    int max_val = INT_MIN;
    for (int i = 1; i <= n; i++) {
        max_val = max(max_val, price[i-1] + cutRod(price, n - i));
    }
    return max_val;
}

int main() {
    vector<int> price = {1, 5, 8, 9};
    int n = 4;
    cout << cutRod(price, n) << endl;
    return 0;
}

A 10

B 9

C 8

D 5

💡 Hint

Think about all possible ways to cut the rod and sum the prices.

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 bottom-up dynamic programming solution for rod cutting with prices {2, 5, 7, 8} and rod length 4?

DSA C++

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int cutRodDP(const vector<int>& price, int n) {
    vector<int> dp(n+1, 0);
    for (int i = 1; i <= n; i++) {
        int max_val = INT_MIN;
        for (int j = 1; j <= i; j++) {
            max_val = max(max_val, price[j-1] + dp[i-j]);
        }
        dp[i] = max_val;
    }
    return dp[n];
}

int main() {
    vector<int> price = {2, 5, 7, 8};
    int n = 4;
    cout << cutRodDP(price, n) << endl;
    return 0;
}

A 9

B 8

C 10

D 7

💡 Hint

Check all possible cuts and use previously computed results.

The best revenue is cutting into two pieces of length 2 each priced 5, total 10.

🔧 Debug

advanced

Identify the Bug in Memoized Rod Cutting

What error will this C++ code produce when running the memoized rod cutting function?

DSA C++

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int cutRodMemo(const vector<int>& price, int n, vector<int>& memo) {
    if (n <= 0) return 0;
    if (memo[n] != -1) return memo[n];
    int max_val = INT_MIN;
    for (int i = 1; i <= n; i++) {
        max_val = max(max_val, price[i-1] + cutRodMemo(price, n - i, memo));
    }
    memo[n] = max_val;
    return max_val;
}

int main() {
    vector<int> price = {1, 5, 8, 9};
    int n = 4;
    vector<int> memo(n+1, -1);
    cout << cutRodMemo(price, n, memo) << endl;
    return 0;
}

A Output: 10

B Runtime error: out_of_range exception

C Compilation error: missing return statement

D Output: 9

💡 Hint

Check the size of the memo vector and how it is accessed.

The memo vector is of size n=4 but accessed at index n=4 which is out of range (valid indices 0-3).

🧠 Conceptual

advanced

Time Complexity of Rod Cutting Algorithms

What is the time complexity of the naive recursive rod cutting solution for a rod of length n?

A O(n^2)

B O(n log n)

C O(n)

D O(2^n)

💡 Hint

Consider how many recursive calls are made without memoization.

The naive recursive solution explores all possible cuts, leading to exponential calls.

🚀 Application

expert

Maximum Revenue and Cuts for Rod Cutting

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

DSA C++

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <utility>
using namespace std;

pair<int, vector<int>> cutRodWithSolution(const vector<int>& price, int n) {
    vector<int> dp(n+1, 0);
    vector<int> cuts(n+1, 0);
    for (int i = 1; i <= n; i++) {
        int max_val = INT_MIN;
        for (int j = 1; j <= i; j++) {
            if (max_val < price[j-1] + dp[i-j]) {
                max_val = price[j-1] + dp[i-j];
                cuts[i] = j;
            }
        }
        dp[i] = max_val;
    }
    vector<int> resultCuts;
    int length = n;
    while (length > 0) {
        resultCuts.push_back(cuts[length]);
        length -= cuts[length];
    }
    return {dp[n], resultCuts};
}

int main() {
    vector<int> price = {1, 5, 10, 9, 10};
    int n = 5;
    auto result = cutRodWithSolution(price, n);
    cout << "Max Revenue: " << result.first << "\nCuts: ";
    for (int c : result.second) cout << c << " ";
    cout << endl;
    return 0;
}

A

Max Revenue: 15
Cuts: 2 3 

B

Max Revenue: 14
Cuts: 1 4 

C

Max Revenue: 13
Cuts: 5 

D

Max Revenue: 16
Cuts: 1 1 3 

💡 Hint

Check all cut combinations and their total prices.

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

Practice

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

easy

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

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

C. To find the shortest rod length possible

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 maximum total price from selling those pieces.

2. Step 2: Identify the 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 A

4. Quick Check:

   Maximize profit = maximize total price [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 a rod of length 5 in C++?

easy

A. int price[4] = {2, 5, 7, 8, 10};

B. int price[] = {2, 5, 7, 8, 10};

C. int price[6] = {0, 2, 5, 7, 8, 10};

D. int price[5] = (2, 5, 7, 8, 10);

Solution

1. Step 1: Understand array declaration in C++

   When size is omitted, the compiler infers it from initializer list length.

2. Step 2: Check each option

   int price[4] = {2, 5, 7, 8, 10}; declares size 4 but initializes 5 elements - invalid syntax (too many initializers). int price[] = {2, 5, 7, 8, 10}; omits size, compiler infers size 5 - correct and flexible. int price[6] = {0, 2, 5, 7, 8, 10}; declares size 6 but initializes 6 elements including 0 at start - usually price array starts at index 0 or 1, but this is uncommon. int price[5] = (2, 5, 7, 8, 10); uses parentheses instead of braces - invalid syntax.

3. Final Answer:

   int price[] = {2, 5, 7, 8, 10}; -> Option B

4. Quick Check:

   Array size inferred from initializer [OK]

Hint: Use braces {} for array initialization, omit size for flexibility [OK]

Common Mistakes:

• Using parentheses instead of braces
• Mismatching array size and initializer count
• Including extra zero element unnecessarily

3. What is the output of the following C++ code snippet for rod length 4?

int price[] = {1, 5, 8, 9};
int n = 4;
int dp[5] = {0};
for (int i = 1; i <= n; i++) {
  int max_val = 0;
  for (int j = 0; j < i; j++) {
    max_val = std::max(max_val, price[j] + dp[i - j - 1]);
  }
  dp[i] = max_val;
}
std::cout << dp[n] << std::endl;

medium

A. 10

B. 9

C. 8

D. 11

Solution

1. Step 1: Trace dp array calculation for n=4

   Calculate dp[1] to dp[4]:
   dp[1] = max(price[0]+dp[0]) = 1+0=1
   dp[2] = max(price[0]+dp[1], price[1]+dp[0]) = max(1+1, 5+0)=5
   dp[3] = max(price[0]+dp[2], price[1]+dp[1], price[2]+dp[0]) = max(1+5, 5+1, 8+0)= max(6,6,8)=8
   dp[4] = max(price[0]+dp[3], price[1]+dp[2], price[2]+dp[1], price[3]+dp[0]) = max(1+8, 5+5, 8+1, 9+0) = max(9,10,9,9)=10

2. Step 2: Verify final dp value

   dp[4] = 10, so output is 10.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   dp[4] = 10 from max cuts [OK]

Hint: Calculate dp values stepwise from smaller lengths [OK]

Common Mistakes:

• Off-by-one errors in indexing
• Ignoring dp array values in calculation
• Confusing price array indexing

4. Identify the error in this C++ code snippet for rod cutting:

int price[] = {2, 5, 7, 8};
int n = 4;
int dp[4] = {0};
for (int i = 1; i <= n; i++) {
  int max_val = 0;
  for (int j = 0; j < i; j++) {
    max_val = std::max(max_val, price[j] + dp[i - j - 1]);
  }
  dp[i] = max_val;
}
std::cout << dp[n] << std::endl;

medium

A. std::max function is used incorrectly

B. Price array is missing an element for length 4

C. Loop variables i and j are swapped incorrectly

D. Array dp size is too small, causing out-of-bounds access

Solution

1. Step 1: Check dp array size and indexing

   dp is declared with size 4 but accessed at dp[i] where i goes up to 4, causing out-of-bounds access since valid indices are 0 to 3.

2. Step 2: Confirm other parts are correct

   Price array has 4 elements matching rod length. Loop variables and std::max usage are correct.

3. Final Answer:

   Array dp size is too small, causing out-of-bounds access -> Option D

4. Quick Check:

   dp size must be n+1 to avoid overflow [OK]

Hint: Declare dp array size as n+1 to avoid index errors [OK]

Common Mistakes:

• Using dp array size equal to n instead of n+1
• Ignoring array bounds in loops
• Misusing std::max parameters

5. Given a rod of length 5 and prices price = {2, 5, 7, 8, 10}, what is the maximum profit and the cuts to achieve it?

hard

A. Maximum profit 14 by cuts: 2 + 2 + 1

B. Maximum profit 13 by cuts: 1 + 4

C. Maximum profit 12 by cuts: 2 + 3

D. Maximum profit 15 by cuts: 1 + 1 + 3

Solution

1. Step 1: Calculate maximum profit using dp

   Calculate dp for length 5:
   dp[1]=2
   dp[2]=max(2+dp[0],5+dp[0])=5
   dp[3]=max(2+dp[1],5+dp[1],7+dp[0])=max(2+2,5+2,7)=7
   dp[4]=max(2+dp[2],5+dp[2],7+dp[1],8+dp[0])=max(2+5,5+5,7+2,8)=10
   dp[5]=max(2+dp[3],5+dp[3],7+dp[2],8+dp[1],10+dp[0])=max(2+7,5+7,7+5,8+2,10)=max(9,12,12,10,10)=12

2. Step 2: Check cuts for maximum profit

   Maximum profit 14 by cuts: 2 + 2 + 1 says profit 14 with cuts 2+2+1. Let's verify:
   Cut 2: price 5
   Cut 2: price 5
   Cut 1: price 2
   Total = 5+5+2=12, not 14.
   Check Maximum profit 15 by cuts: 1 + 1 + 3: 1+1+3 cuts:
   1:2,1:2,3:7 total=11
   Maximum profit 13 by cuts: 1 + 4: 1+4 cuts:
   1:2,4:8 total=10
   Maximum profit 12 by cuts: 2 + 3: 2+3 cuts:
   2:5,3:7 total=12
   So maximum profit is 12, cuts can be 2+3 or 2+2+1.
   Maximum profit 14 by cuts: 2 + 2 + 1 says 14 profit which is incorrect.
   Maximum profit 12 by cuts: 2 + 3 says 12 profit with cuts 2+3 which is correct.

3. Final Answer:

   Maximum profit 12 by cuts: 2 + 3 -> Option C

4. Quick Check:

   Max profit = 12 by cuts 2+3 [OK]

Hint: Try all cut combinations to find max profit [OK]

Common Mistakes:

• Adding prices incorrectly for cuts
• Assuming single cut gives max profit
• Ignoring multiple cut combinations