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.

Practice

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

easy

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

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

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

D. To find the shortest rod length possible

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 C

4. Quick Check:

   Maximize profit = maximize total price [OK]

Hint: Focus on maximizing profit from pieces, not cuts or counts [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 TypeScript function signatures correctly represents the rod cutting problem function?

easy

A. function rodCutting(prices: string[], length: number): number

B. function rodCutting(length: number, prices: number[]): void

C. function rodCutting(prices: number[], length: number): string

D. function rodCutting(prices: number[], length: number): number

Solution

1. Step 1: Analyze function parameters and return type

   The function should take an array of prices (number[]) and the rod length (number), returning the maximum profit (number).

2. Step 2: Match correct signature

   function rodCutting(prices: number[], length: number): number matches this: prices array first, length second, returns number.

3. Final Answer:

   function rodCutting(prices: number[], length: number): number -> Option D

4. Quick Check:

   Input: prices array, length; Output: number [OK]

Hint: Function returns max profit as number, inputs are prices array and length [OK]

Common Mistakes:

• Swapping parameter order
• Returning void or string instead of number
• Using wrong parameter types like string[] for prices

3. What is the output of the following TypeScript code for rod cutting?

const prices = [1, 5, 8, 9];
const length = 4;
function rodCutting(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] + rodCutting(prices, n - i));
  }
  return maxVal;
}
console.log(rodCutting(prices, length));

medium

A. 10

B. 9

C. 11

D. 8

Solution

1. Step 1: Understand recursive calls and prices

   Prices for lengths 1 to 4 are [1,5,8,9]. The function tries all cuts and sums prices recursively.

2. Step 2: Calculate max profit for length 4

   Possible cuts:
   - 1 + rodCutting(3) = 1 + 8 = 9
   - 5 + rodCutting(2) = 5 + 5 = 10
   - 8 + rodCutting(1) = 8 + 1 = 9
   - 9 + rodCutting(0) = 9 + 0 = 9
   rodCutting(2) = max(1+rodCutting(1),5+rodCutting(0)) = max(1+1,5+0)=5
   rodCutting(3) = max(1+rodCutting(2),5+rodCutting(1),8+rodCutting(0)) = max(1+5,5+1,8+0)= max(6,6,8)=8
   So max is 10.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Max profit for length 4 = 10 [OK]

Hint: Try all cuts recursively, pick max sum [OK]

Common Mistakes:

• Ignoring recursive calls
• Using wrong indices for prices
• Assuming max is price of full length only

4. Identify the bug in this TypeScript rod cutting function:

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

medium

A. Loop should run until i <= n, not i < n

B. Base case should return -Infinity instead of 0

C. prices array indexing is off by one

D. Function should return void, not number

Solution

1. Step 1: Check loop range correctness

   The loop runs from i = 1 to i < n, so it misses the case when i = n (full length cut).

2. Step 2: Fix loop to include full length cut

   Changing loop condition to i <= n ensures all cuts including full length are considered.

3. Final Answer:

   Loop should run until i <= n, not i < n -> Option A

4. Quick Check:

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

Hint: Loop must include full length cut (i <= n) [OK]

Common Mistakes:

• Using i < n misses full rod cut
• Changing base case incorrectly
• Misindexing prices array

5. Given a rod of length 5 and prices array [2, 5, 7, 8, 10], what is the maximum profit using dynamic programming approach?

hard

A. 13

B. 12

C. 14

D. 15

Solution

1. Step 1: Use bottom-up DP to find max profit

   Prices: length 1=2, 2=5, 3=7, 4=8, 5=10.
   Calculate max profit for each length:
   dp[0]=0
   dp[1]=max(2)=2
   dp[2]=max(2+dp[1],5)=max(2+2,5)=5
   dp[3]=max(2+dp[2],5+dp[1],7)=max(2+5,5+2,7)=7
   dp[4]=max(2+dp[3],5+dp[2],7+dp[1],8)=max(2+7,5+5,7+2,8)=max(9,10,9,8)=10
   dp[5]=max(2+dp[4],5+dp[3],7+dp[2],8+dp[1],10)=max(2+10,5+7,7+5,8+2,10)=max(12,12,12,10,10)=12
   Therefore, correct answer is 12.

2. Final Answer:

   12 -> Option B

3. Quick Check:

   DP max profit for length 5 = 12 [OK]

Hint: Use bottom-up DP, check all cuts for max profit [OK]

Common Mistakes:

• Ignoring smaller cuts combinations
• Miscomputing dp array values
• Assuming price of full length is max