Rod Cutting Problem in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Rod Cutting Maximum Revenue Calculation

What is the output of the following Go code that calculates the maximum revenue for a rod of length 4 with given prices?

DSA Go

package main
import "fmt"
func rodCutting(prices []int, n int) int {
    if n == 0 {
        return 0
    }
    maxVal := -1
    for i := 1; i <= n; i++ {
        val := prices[i-1] + rodCutting(prices, n-i)
        if val > maxVal {
            maxVal = val
        }
    }
    return maxVal
}
func main() {
    prices := []int{1, 5, 8, 9}
    length := 4
    fmt.Println(rodCutting(prices, length))
}

A 7

B 9

C 10

D 8

💡 Hint

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

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

❓ Predict Output

intermediate

Output of Bottom-Up Rod Cutting Implementation

What is the output of this Go code that uses bottom-up dynamic programming to find maximum revenue for rod length 5?

DSA Go

package main
import "fmt"
func rodCutting(prices []int, n int) int {
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        maxVal := -1
        for j := 1; j <= i; j++ {
            val := prices[j-1] + dp[i-j]
            if val > maxVal {
                maxVal = val
            }
        }
        dp[i] = maxVal
    }
    return dp[n]
}
func main() {
    prices := []int{2, 5, 7, 8, 10}
    length := 5
    fmt.Println(rodCutting(prices, length))
}

A 12

B 15

C 14

D 10

💡 Hint

Check all possible cuts and use previously computed results.

The best revenue for length 5 is 12, achieved by cutting into lengths 2 and 3 (5 + 7).

🔧 Debug

advanced

Identify the Error in Recursive Rod Cutting Code

What error does the following Go code produce when run?

DSA Go

package main
import "fmt"
func rodCutting(prices []int, n int) int {
    if n == 0 {
        return 0
    }
    maxVal := 0
    for i := 1; i <= n; i++ {
        val := prices[i] + rodCutting(prices, n-i)
        if val > maxVal {
            maxVal = val
        }
    }
    return maxVal
}
func main() {
    prices := []int{1, 5, 8, 9}
    length := 4
    fmt.Println(rodCutting(prices, length))
}

A runtime error: index out of range

B compilation error: missing return statement

C output: 10

D output: 9

💡 Hint

Check array indexing carefully inside the loop.

The code accesses prices[i] where i can be equal to n, causing index out of range error.

🧠 Conceptual

advanced

Time Complexity of Rod Cutting Recursive Solution

What is the time complexity of the naive recursive rod cutting solution without memoization for 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 combinations, leading to exponential time O(2^n).

🚀 Application

expert

Maximum Revenue and Cuts for Rod Cutting

Given prices for rod lengths and a rod length of 7, which option correctly shows the maximum revenue and the cuts to achieve it?

DSA Go

prices := []int{1, 5, 8, 9, 10, 17, 17}
length := 7

A {"max_revenue": 18, "cuts": [1, 6]}

B {"max_revenue": 18, "cuts": [2, 2, 3]}

C {"max_revenue": 19, "cuts": [3, 4]}

D {"max_revenue": 17, "cuts": [7]}

💡 Hint

Try all cut combinations and sum their prices.

Cutting into lengths 2, 2, 3 yields 5 + 5 + 8 = 18 revenue, which is maximum.

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 maximize the total profit by cutting the rod into pieces

C. To find the shortest rod length possible

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

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 B

4. Quick Check:

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

Hint: Focus on maximizing profit, not minimizing cuts or counting ways [OK]

Common Mistakes:

• Thinking the goal is to minimize cuts
• Confusing with counting number of ways
• Assuming shortest rod length is the goal

2. Which of the following Go function signatures correctly represents a rod cutting function that takes rod length and price slice as input and returns maximum profit as int?

easy

A. func rodCutting(prices int, length []int) int

B. func rodCutting(prices []int, length int) bool

C. func rodCutting(length int, prices []int) string

D. func rodCutting(length int, prices []int) int

Solution

1. Step 1: Analyze parameter types and order

   The rod length should be an int, prices should be a slice of ints ([]int), and return type should be int for max profit.

2. Step 2: Match correct signature

   func rodCutting(length int, prices []int) int matches: func rodCutting(length int, prices []int) int

3. Final Answer:

   func rodCutting(length int, prices []int) int -> Option D

4. Quick Check:

   Correct parameter types and return int = func rodCutting(length int, prices []int) int [OK]

Hint: Remember: length int, prices []int, return int for profit [OK]

Common Mistakes:

• Swapping parameter order
• Wrong return type like string or bool
• Using incorrect parameter types

3. What will be the output of the following Go code snippet for rod length 4 and prices [1, 5, 8, 9]?

package main

import "fmt"

func rodCutting(n int, prices []int) int {
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        maxVal := 0
        for j := 1; j <= i; j++ {
            val := prices[j-1] + dp[i-j]
            if val > maxVal {
                maxVal = val
            }
        }
        dp[i] = maxVal
    }
    return dp[n]
}

func main() {
    prices := []int{1, 5, 8, 9}
    result := rodCutting(4, prices)
    fmt.Println(result)
}

medium

A. 8

B. 9

C. 10

D. 11

Solution

1. Step 1: Understand the dp array calculation

   dp[i] stores max profit for rod length i. For length 4, check all cuts: - Cut 1: price 1 + dp[3] = 1 + 8 = 9 - Cut 2: price 5 + dp[2] = 5 + 5 = 10 - Cut 3: price 8 + dp[1] = 8 + 1 = 9 - Cut 4: price 9 + dp[0] = 9 + 0 = 9

2. Step 2: Calculate dp values stepwise

   dp[1]=1, dp[2]=5, dp[3]=8, dp[4]=max(9,10,9,9)=10 But re-check dp[3]: - Cut 1: 1 + dp[2]=1+5=6 - Cut 2: 5 + dp[1]=5+1=6 - Cut 3: 8 + dp[0]=8+0=8 So dp[3]=8 Now dp[4]: - Cut 1: 1 + dp[3]=1+8=9 - Cut 2: 5 + dp[2]=5+5=10 - Cut 3: 8 + dp[1]=8+1=9 - Cut 4: 9 + dp[0]=9+0=9 Max is 10

3. Final Answer:

   10 -> Option C

4. Quick Check:

   Max profit for length 4 = 10 [OK]

Hint: Calculate dp array stepwise checking all cuts [OK]

Common Mistakes:

• Ignoring dp values for smaller lengths
• Choosing wrong max profit among cuts
• Confusing indices in prices slice

4. Identify the bug in the following Go code for rod cutting and select the correct fix:

func rodCutting(n int, prices []int) int {
    dp := make([]int, n)
    for i := 1; i <= n; i++ {
        maxVal := 0
        for j := 1; j <= i; j++ {
            val := prices[j-1] + dp[i-j]
            if val > maxVal {
                maxVal = val
            }
        }
        dp[i] = maxVal
    }
    return dp[n]
}

medium

A. Change dp size to n+1 and access dp[i] safely

B. Change loop to start from i := 0 instead of 1

C. Remove inner loop and use only prices[i-1]

D. Change return to dp[n-1] instead of dp[n]

Solution

1. Step 1: Identify index out of range error

   dp slice is size n but code accesses dp[i] where i can be n, causing out of range error.

2. Step 2: Fix dp size to n+1

   Make dp size n+1 to safely store dp[n] and avoid index errors.

3. Final Answer:

   Change dp size to n+1 and access dp[i] safely -> Option A

4. Quick Check:

   dp size must be n+1 for dp[n] access [OK]

Hint: dp array size must be n+1 to avoid index errors [OK]

Common Mistakes:

• Using dp size n causes index out of range
• Changing loop start incorrectly
• Removing inner loop breaks logic

5. Given a rod of length 5 and prices [2, 5, 7, 8, 10], what is the maximum profit and the cuts to achieve it using the rod cutting problem approach?

hard

A. Max profit 12 by cuts [2,3]

B. Max profit 11 by cuts [1,4]

C. Max profit 13 by cuts [1,1,3]

D. Max profit 10 by cuts [5]

Solution

1. Step 1: Calculate max profit dp array

   dp[0] = 0
   dp[1] = max(prices[0] + dp[0]) = 2 + 0 = 2
   dp[2] = max(2 + dp[1] = 4, 5 + dp[0] = 5) = 5
   dp[3] = max(2 + dp[2] = 7, 5 + dp[1] = 7, 7 + dp[0] = 7) = 7
   dp[4] = max(2 + dp[3] = 9, 5 + dp[2] = 10, 7 + dp[1] = 9, 8 + dp[0] = 8) = 10
   dp[5] = max(2 + dp[4] = 12, 5 + dp[3] = 12, 7 + dp[2] = 12, 8 + dp[1] = 10, 10 + dp[0] = 10) = 12

2. Step 2: Identify cuts for max profit 12

   Max profit 12 achieved by cuts [2,3] or [3,2]. Prices 5 + 7 = 12.

3. Final Answer:

   Max profit 12 by cuts [2,3] -> Option A

4. Quick Check:

   Max profit 12 with cuts 2 and 3 [OK]

Hint: Calculate dp and track cuts for max profit [OK]

Common Mistakes:

• Not checking all cut combinations
• Assuming single cut is best
• Ignoring dp values for smaller lengths