Rod Cutting Problem in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Rod Cutting

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

DSA Typescript

function cutRod(prices: number[], n: number): number {
  if (n <= 0) return 0;
  let maxVal = -Infinity;
  for (let i = 1; i <= n; i++) {
    maxVal = Math.max(maxVal, prices[i - 1] + cutRod(prices, n - i));
  }
  return maxVal;
}

const prices = [1, 5, 8, 9];
const length = 4;
console.log(cutRod(prices, length));

A 9

B 10

C 8

D 5

💡 Hint

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

The maximum revenue for length 4 is 10, achieved by cutting into lengths 2 and 2 (5 + 5).

❓ Predict Output

intermediate

Output of Memoized Rod Cutting

What is the output of this TypeScript code using memoization for rod cutting with prices [2, 5, 7, 8] and rod length 3?

DSA Typescript

function memoizedCutRod(prices: number[], n: number, memo: number[] = []): number {
  if (n <= 0) return 0;
  if (memo[n] !== undefined) return memo[n];
  let maxVal = -Infinity;
  for (let i = 1; i <= n; i++) {
    maxVal = Math.max(maxVal, prices[i - 1] + memoizedCutRod(prices, n - i, memo));
  }
  memo[n] = maxVal;
  return maxVal;
}

const prices = [2, 5, 7, 8];
const length = 3;
console.log(memoizedCutRod(prices, length));

A 8

B 14

C 12

D 7

💡 Hint

Memoization stores results to avoid repeated work.

Maximum revenue for length 3 is 12, by cutting into lengths 1 and 2 (2 + 5) or length 3 (7) plus smaller cuts.

🔧 Debug

advanced

Identify the Error in Bottom-Up Rod Cutting

What error does this TypeScript code produce when trying to solve the rod cutting problem using bottom-up dynamic programming?

DSA Typescript

function bottomUpCutRod(prices: number[], n: number): number {
  const dp = new Array(n + 1).fill(0);
  for (let j = 1; j <= n; j++) {
    let maxVal = -Infinity;
    for (let i = 1; i <= j; i++) {
      maxVal = Math.max(maxVal, prices[i] + dp[j - i]);
    }
    dp[j] = maxVal;
  }
  return dp[n];
}

const prices = [1, 5, 8, 9];
const length = 4;
console.log(bottomUpCutRod(prices, length));

A TypeError: Cannot read property '4' of undefined

B Output: 9

C SyntaxError: Unexpected token

D Output: 10

💡 Hint

Check array indexing carefully inside the inner loop.

The code uses prices[i] but prices is zero-indexed, so prices[4] is undefined causing TypeError.

❓ Predict Output

advanced

Output of Bottom-Up Rod Cutting Corrected

What is the output of this corrected bottom-up rod cutting code for prices [1, 5, 8, 9] and rod length 4?

DSA Typescript

function bottomUpCutRod(prices: number[], n: number): number {
  const dp = new Array(n + 1).fill(0);
  for (let j = 1; j <= n; j++) {
    let maxVal = -Infinity;
    for (let i = 1; i <= j; i++) {
      maxVal = Math.max(maxVal, prices[i - 1] + dp[j - i]);
    }
    dp[j] = maxVal;
  }
  return dp[n];
}

const prices = [1, 5, 8, 9];
const length = 4;
console.log(bottomUpCutRod(prices, length));

A 5

B 9

C 8

D 10

💡 Hint

Bottom-up builds solutions from smaller lengths up to n.

The maximum revenue for length 4 is 10, achieved by cutting into two pieces of length 2 (5 + 5).

🧠 Conceptual

expert

Time Complexity of Rod Cutting Algorithms

Which statement correctly describes the time complexity of the naive recursive, memoized, and bottom-up solutions for the rod cutting problem of length n?

A Naive recursive: exponential, Memoized: O(n^2), Bottom-up: O(n^2)

B Naive recursive: O(n), Memoized: O(n), Bottom-up: O(n)

C Naive recursive: O(n^2), Memoized: exponential, Bottom-up: O(n^2)

D Naive recursive: O(n^2), Memoized: O(n^2), Bottom-up: exponential

💡 Hint

Consider how many subproblems each approach solves and how often.

Naive recursion solves overlapping subproblems repeatedly causing exponential time. Memoization and bottom-up solve each subproblem once, each taking O(n^2) time due to nested loops.