Rod Cutting Problem in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the maximum revenue array with zeros.

DSA Typescript

const maxRevenue: number[] = new Array(n + 1).fill([1]);

Drag options to blanks, or click blank then click option'

A1

Bnull

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing with 1 instead of 0 causes incorrect revenue calculations.

Using null or -1 can cause runtime errors when adding revenues.

We initialize the maxRevenue array with zeros because initially, the maximum revenue for all lengths is zero.

2fill in blank

medium

Complete the code to loop through all possible first cut lengths.

DSA Typescript

for (let i = 1; i <= [1]; i++) {

Drag options to blanks, or click blank then click option'

An

Blength

Cprice.length

DmaxRevenue.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using price.length causes incorrect loop bounds.

Using maxRevenue.length is off by one due to array size.

We loop from 1 to n because n is the total length of the rod, and we consider all possible first cuts.

3fill in blank

hard

Fix the error in updating the maximum revenue inside the nested loop.

DSA Typescript

maxRevenue[j] = Math.max(maxRevenue[j], price[i - 1] + [1]);

Drag options to blanks, or click blank then click option'

AmaxRevenue[j - i]

BmaxRevenue[i]

Cprice[j - i]

Dprice[j]

Attempts:

3 left

💡 Hint

Common Mistakes

Adding price[j - i] instead of maxRevenue[j - i] causes wrong revenue calculation.

Using maxRevenue[i] ignores the remaining length.

We add the price of the first cut (price[i - 1]) to the maximum revenue of the remaining length (maxRevenue[j - i]).

4fill in blank

hard

Fill both blanks to complete the nested loop for calculating max revenue.

DSA Typescript

for (let j = [1]; j <= n; j++) {
  maxRevenue[j] = Math.max(maxRevenue[j], price[i - 1] + [2]);
}

Drag options to blanks, or click blank then click option'

Ai

Bj

Cj - i

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Starting j from 1 instead of i causes invalid cuts.

Adding maxRevenue[j] instead of maxRevenue[j - i] causes wrong results.

The inner loop starts from i because we cannot cut a piece longer than j. We add price[i - 1] to maxRevenue[j - i] for the remaining length.

5fill in blank

hard

Fill all three blanks to complete the rod cutting function.

DSA Typescript

function rodCutting(price: number[], n: number): number {
  const maxRevenue: number[] = new Array(n + 1).fill([1]);
  for (let i = 1; i <= [2]; i++) {
    for (let j = i; j <= n; j++) {
      maxRevenue[j] = Math.max(maxRevenue[j], price[i - 1] + [3]);
    }
  }
  return maxRevenue[n];
}

Drag options to blanks, or click blank then click option'

A0

Bn

CmaxRevenue[j - i]

Dprice.length

Attempts:

3 left

💡 Hint

Common Mistakes

Incorrect initialization of maxRevenue.

Wrong loop bounds for i.

Adding price[j] instead of maxRevenue[j - i].

Initialize maxRevenue with 0, loop i from 1 to n, and update maxRevenue[j] by adding price[i - 1] to maxRevenue[j - i].