Rod Cutting Problem in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Rod Cutting

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

DSA Javascript

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

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

A 9

B 10

C 13

D 8

💡 Hint

Think about all possible cuts and their combinations to maximize the price.

The function tries all cuts from length 1 to n and recursively calculates the best price. For prices [1,5,8,9,10] and rod length 5, the best price is 13 by cutting into lengths 2 and 3 (5 + 8).

❓ Predict Output

intermediate

Output of Memoized Rod Cutting

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

DSA Javascript

function memoizedCutRod(price, n, memo = {}) {
  if (n <= 0) return 0;
  if (memo[n]) return memo[n];
  let max_val = -Infinity;
  for (let i = 1; i <= n; i++) {
    max_val = Math.max(max_val, price[i - 1] + memoizedCutRod(price, n - i, memo));
  }
  memo[n] = max_val;
  return max_val;
}

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

A 10

B 9

C 8

D 7

💡 Hint

Memoization stores results to avoid repeated calculations.

The best price for rod length 4 with prices [2,5,7,8] is 10 by cutting into two pieces of length 2 (5 + 5).

🔧 Debug

advanced

Identify the Bug in Bottom-Up Rod Cutting

The following code is intended to solve the rod cutting problem using a bottom-up dynamic programming approach. What is the bug that causes incorrect output?

DSA Javascript

function bottomUpCutRod(price, n) {
  let val = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    let max_val = -Infinity;
    for (let j = 1; j < i; j++) {
      max_val = Math.max(max_val, price[j - 1] + val[i - j]);
    }
    val[i] = max_val;
  }
  return val[n];
}

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

A The function returns val[n-1] instead of val[n]

B The inner loop should run j <= i instead of j < i

C The array val should be initialized with -Infinity instead of 0

D The price array is accessed with wrong indices causing undefined values

💡 Hint

Check the loop boundaries carefully.

The inner loop runs from j=1 to j < i, so it misses the case when j equals i, which is needed to consider the whole rod without cutting.

🧠 Conceptual

advanced

Time Complexity of Rod Cutting Algorithms

Which of the following correctly describes the time complexity of the naive recursive and the dynamic programming solutions for the rod cutting problem of length n?

A Naive recursive: O(n^2), Dynamic programming: O(n log n)

B Naive recursive: O(n!), Dynamic programming: O(n)

C Naive recursive: O(n), Dynamic programming: O(n^2)

D Naive recursive: exponential, Dynamic programming: O(n^2)

💡 Hint

Consider how many subproblems are solved repeatedly in recursion.

The naive recursive approach solves overlapping subproblems repeatedly, leading to exponential time. The dynamic programming approach solves each subproblem once, resulting in O(n^2) time.

🚀 Application

expert

Maximum Revenue and Cuts for Rod Cutting

Given the prices array and rod length, which option correctly returns both the maximum revenue and the list of cuts to achieve it using bottom-up dynamic programming?

DSA Javascript

function extendedBottomUpCutRod(price, n) {
  let val = new Array(n + 1).fill(0);
  let cuts = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    let max_val = -Infinity;
    for (let j = 1; j <= i; j++) {
      if (max_val < price[j - 1] + val[i - j]) {
        max_val = price[j - 1] + val[i - j];
        cuts[i] = j;
      }
    }
    val[i] = max_val;
  }
  let resultCuts = [];
  let length = n;
  while (length > 0) {
    resultCuts.push(cuts[length]);
    length -= cuts[length];
  }
  return { maxRevenue: val[n], cuts: resultCuts };
}

const prices = [1, 5, 8, 9, 10];
console.log(extendedBottomUpCutRod(prices, 5));

A {"maxRevenue":13,"cuts":[2,3]}

B {"maxRevenue":10,"cuts":[5]}

C {"maxRevenue":13,"cuts":[3,2]}

D {"maxRevenue":9,"cuts":[4,1]}

💡 Hint

Trace the cuts array to find the sequence of cuts that yield max revenue.

The maximum revenue is 13 by cutting the rod into lengths 2 and 3. The cuts array stores the first cut length for each rod length, so the sequence is [2,3].

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 find the shortest rod length possible

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

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 D

4. Quick Check:

   Maximize profit = To maximize the total profit by cutting the rod into pieces [OK]

Hint: Remember: maximize profit, not minimize cuts [OK]

Common Mistakes:

• Thinking the goal is to minimize cuts
• Confusing number of ways with maximum profit
• Assuming rod length is to be minimized

2. Which of the following is the correct way to declare a function in JavaScript to solve the rod cutting problem?

easy

A. function rodCutting(prices, n) { /* code */ }

B. def rodCutting(prices, n): /* code */

C. func rodCutting(prices, n) { /* code */ }

D. rodCutting function(prices, n) { /* code */ }

Solution

1. Step 1: Identify JavaScript function syntax

   JavaScript functions are declared using the function keyword followed by the name and parameters.

2. Step 2: Check each option

   function rodCutting(prices, n) { /* code */ } uses correct JavaScript syntax. def rodCutting(prices, n): /* code */ is Python, C is Go/Swift style, D is invalid.

3. Final Answer:

   function rodCutting(prices, n) { /* code */ } -> Option A

4. Quick Check:

   JS function syntax = function rodCutting(prices, n) { /* code */ } [OK]

Hint: JS functions start with 'function' keyword [OK]

Common Mistakes:

• Using Python or other language syntax
• Missing 'function' keyword
• Incorrect parameter declaration

3. What will be the output of the following code snippet?

const prices = [1, 5, 8, 9];
function rodCutting(prices, n) {
  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, 4));

medium

A. 8

B. 9

C. 10

D. 15

Solution

1. Step 1: Understand the recursive calls for n=4

   Calculate max profit for rod length 4 by checking all cuts:
   - Cut 1: price[0] + rodCutting(3) = 1 + 8 = 9
   - Cut 2: price[1] + rodCutting(2) = 5 + 5 = 10
   - Cut 3: price[2] + rodCutting(1) = 8 + 1 = 9
   - Cut 4: price[3] + rodCutting(0) = 9 + 0 = 9

2. Step 2: Calculate rodCutting(3), rodCutting(2), rodCutting(1)

   rodCutting(3) = max(1+5=6, 5+1=6, 8+0=8) = 8
   rodCutting(2) = max(1+1=2, 5+0=5) = 5
   rodCutting(1) = 1

3. Final Answer:

   10 -> Option C

4. Quick Check:

   Max profit for length 4 = 10 [OK]

Hint: Check all cuts and pick max sum recursively [OK]

Common Mistakes:

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

4. Identify the error in the following rod cutting function and select the fix:

function rodCutting(prices, n) {
  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. Change loop condition to i <= n

B. Initialize maxVal to -Infinity

C. Change base case to if (n === 0) return 1

D. Remove recursive call inside loop

Solution

1. Step 1: Analyze loop range

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

2. Step 2: Fix loop condition

   Changing to i <= n includes the full rod cut option, ensuring all possibilities are checked.

3. Final Answer:

   Change loop condition to i <= n -> Option A

4. Quick Check:

   Loop must include full length cut = Change loop condition to i <= n [OK]

Hint: Loop must cover full rod length cuts [OK]

Common Mistakes:

• Using i < n instead of i <= n
• Incorrect base case return value
• Removing recursion breaks logic

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. 14

B. 17

C. 15

D. 12

Solution

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

   Calculate max profit for lengths 1 to 5:
   Length 1: max = 2
   Length 2: max = max(5, 2+2) = 5
   Length 3: max = max(7, 5+2, 2+5) = 7
   Length 4: max = max(8, 7+2, 5+5, 2+7) = 10
   Length 5: max = max(10, 8+2, 7+5, 5+7, 2+10) = 17

2. Step 2: Confirm maximum profit for length 5

   The best cut is length 1 + length 4 (2+15=17) or length 2 + length 3 (5+7=12), so 17 is maximum.

3. Final Answer:

   17 -> Option B

4. Quick Check:

   DP max profit for length 5 = 17 [OK]

Hint: Use DP table from length 1 to n for max profit [OK]

Common Mistakes:

• Not considering all cut combinations
• Using recursive without memoization causing slow results
• Confusing prices index with rod length