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.