Rod Cutting Problem in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Rod Cutting Recursive Solution

What is the output of the following C code that solves the rod cutting problem using a simple recursive approach?

DSA C

#include <stdio.h>

int rodCutting(int price[], int n) {
    if (n <= 0) return 0;
    int max_val = -1;
    for (int i = 1; i <= n; i++) {
        int val = price[i - 1] + rodCutting(price, n - i);
        if (val > max_val) max_val = val;
    }
    return max_val;
}

int main() {
    int price[] = {1, 5, 8, 9};
    int n = 4;
    int result = rodCutting(price, n);
    printf("%d\n", result);
    return 0;
}

A 8

B 9

C 10

D 5

💡 Hint

Think about all possible cuts and their prices.

The maximum revenue for rod length 4 with prices {1,5,8,9} is 10 by cutting into lengths 2 and 2 (5 + 5).

❓ Predict Output

intermediate

Output of Rod Cutting with Memoization

What is the output of this C code that uses memoization to solve the rod cutting problem?

DSA C

#include <stdio.h>
#include <string.h>

int memo[100];

int rodCuttingMemo(int price[], int n) {
    if (n <= 0) return 0;
    if (memo[n] != -1) return memo[n];
    int max_val = -1;
    for (int i = 1; i <= n; i++) {
        int val = price[i - 1] + rodCuttingMemo(price, n - i);
        if (val > max_val) max_val = val;
    }
    memo[n] = max_val;
    return max_val;
}

int main() {
    int price[] = {2, 5, 7, 8};
    int n = 4;
    memset(memo, -1, sizeof(memo));
    int result = rodCuttingMemo(price, n);
    printf("%d\n", result);
    return 0;
}

A 14

B 10

C 16

D 13

💡 Hint

Memoization stores results to avoid repeated work.

The best revenue for length 4 with prices {2,5,7,8} is 10 by cutting into lengths 2 and 2 (5 + 5).

🧠 Conceptual

advanced

Time Complexity of Rod Cutting Recursive Solution

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

A O(n^2)

B O(n)

C O(n!)

D O(2^n)

💡 Hint

Consider how many recursive calls are made for each length.

The naive recursive solution explores all possible cuts, leading to exponential time O(2^n).

❓ Predict Output

advanced

Output of Bottom-Up Rod Cutting DP

What is the output of this bottom-up dynamic programming solution for rod cutting?

DSA C

#include <stdio.h>

int rodCuttingDP(int price[], int n) {
    int dp[n+1];
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        int max_val = -1;
        for (int j = 1; j <= i; j++) {
            int val = price[j - 1] + dp[i - j];
            if (val > max_val) max_val = val;
        }
        dp[i] = max_val;
    }
    return dp[n];
}

int main() {
    int price[] = {3, 5, 8, 9, 10};
    int n = 5;
    int result = rodCuttingDP(price, n);
    printf("%d\n", result);
    return 0;
}

A 18

B 17

C 15

D 16

💡 Hint

Bottom-up DP builds solutions from smaller lengths to larger.

The maximum revenue for length 5 with prices {3,5,8,9,10} is 18 by cutting into lengths 2 and 3 (5 + 8).

🧠 Conceptual

expert

Optimal Substructure in Rod Cutting Problem

Which statement best describes the optimal substructure property in the rod cutting problem?

A The optimal solution for length n depends only on the optimal solutions of smaller lengths.

B The problem cannot be divided into smaller subproblems.

C The solution for length n is independent of solutions for smaller lengths.

D The problem requires checking all permutations of cuts without reuse.

💡 Hint

Optimal substructure means solutions build on smaller solutions.

Rod cutting uses optimal substructure because the best solution for length n uses best solutions for smaller lengths.

Practice

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

easy

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

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

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 highest 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 B

4. Quick Check:

   Maximize profit = maximize total price [OK]

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

Common Mistakes:

• Thinking the goal is to minimize cuts
• Confusing the problem with counting combinations
• Assuming the rod length changes

2. Which of the following is the correct way to declare the price array for a rod of length 4 in C?

easy

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

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

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

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

Solution

1. Step 1: Understand array indexing for rod prices

   Prices are usually stored with index representing length, so for length 1 to 4, index 0 is unused or zero.

2. Step 2: Check array declaration correctness

   int price[5] = {0, 2, 5, 7, 8}; declares array of size 5 with price[0]=0, then prices for lengths 1 to 4, which is correct.

3. Final Answer:

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

4. Quick Check:

   Index 0 unused, prices start at 1 [OK]

Hint: Use size n+1 with zero at index 0 for convenience [OK]

Common Mistakes:

• Using parentheses instead of braces for array initialization
• Declaring array size smaller than needed
• Not including zero price at index 0

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

int price[5] = {0, 2, 5, 7, 8};
int n = 4;
int dp[5] = {0};
for (int i = 1; i <= n; i++) {
  int max_val = 0;
  for (int j = 1; j <= i; j++) {
    int val = price[j] + dp[i - j];
    if (val > max_val) max_val = val;
  }
  dp[i] = max_val;
}
printf("%d", dp[n]);

medium

A. 10

B. 9

C. 8

D. 7

Solution

1. Step 1: Trace dp array computation for each length

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

2. Step 2: Identify final dp[n] value

   dp[4] = 10 is printed.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Max profit for length 4 = 10 [OK]

Hint: Calculate dp bottom-up, check all cuts for max profit [OK]

Common Mistakes:

• Forgetting to consider all cut lengths j
• Using wrong indices for price or dp
• Not initializing dp array properly

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

int price[5] = {0, 2, 5, 7, 8};
int n = 4;
int dp[5] = {0};
for (int i = 1; i <= n; i++) {
  int max_val = 0;
  for (int j = 1; j < i; j++) {
    int val = price[j] + dp[i - j];
    if (val > max_val) max_val = val;
  }
  dp[i] = max_val;
}
printf("%d", dp[n]);

medium

A. max_val should be initialized to -1

B. dp array size is too small

C. price array initialization is incorrect

D. Inner loop should run till j <= i, not j < i

Solution

1. Step 1: Analyze inner loop range

   The inner loop runs from j=1 to j

2. Step 2: Correct the loop condition

   Changing inner loop to j <= i ensures all possible cuts including full length are considered.

3. Final Answer:

   Inner loop should run till j <= i, not j < i -> Option D

4. Quick Check:

   Include full length cut by using j <= i [OK]

Hint: Inner loop must include full length cut (j <= i) [OK]

Common Mistakes:

• Using j < i misses full rod cut
• Incorrect dp array size causes errors
• Initializing max_val to 0 is correct here

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

hard

A. Profit = 12, Cuts = [2, 3]

B. Profit = 11, Cuts = [1, 4]

C. Profit = 10, Cuts = [5]

D. Profit = 13, Cuts = [1, 1, 3]

Solution

1. Step 1: Calculate maximum profit using dp

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

2. Step 2: Determine cuts for maximum profit

   Profit 12 achieved by cutting rod into lengths 2 and 3 (price[2]+price[3]=5+7=12).

3. Final Answer:

   Profit = 12, Cuts = [2, 3] -> Option A

4. Quick Check:

   Max profit 12 with cuts 2 and 3 [OK]

Hint: Check all cut pairs for max sum profit [OK]

Common Mistakes:

• Choosing no cuts or single cut only
• Not checking all combinations for max profit
• Confusing profit values with cut lengths