Maximize The Cut Segments | Practice Medium 0 attempts
GeeksforGeeks ↗

Maximize The Cut Segments | Practice

Medium Dynamic ProgrammingMemoization GeeksforGeeks

You have a rod of length n and three allowed cut lengths x, y, and z. Cut the rod into as many pieces as possible where every piece measures exactly x, y, or z, using up the rod with nothing left over. If there's no way to cut the whole rod into pieces of these lengths, return 0.

Input Format
Implement maximizeTheCutSegments(n, x, y, z). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
n = 4
x = 2
y = 1
z = 1
Output
4

Example 2

Input
n = 7
x = 2
y = 4
z = 6
Output
0
Constraints
  • 1 <= N <= 10^4
  • 1 <= x, y, z <= N
Test Cases (2)
Case 1
Args: [4,2,1,1] Expected: 4
Case 2
Args: [7,2,4,6] Expected: 0
Topics
Dynamic ProgrammingMemoization

Approach: DP (Unbounded Knapsack Variant)

dp[i] stores the maximum number of segments for rod length i. For each length, try cutting with x, y, or z. If the remaining length has a valid solution, update dp[i].

javascript
function maximizeTheCutSegments(n, x, y, z) {
  const dp = new Array(n + 1).fill(-1);
  dp[0] = 0;
  for (let i = 1; i <= n; i++) {
    for (const cut of [x, y, z]) {
      if (i >= cut && dp[i - cut] !== -1)
        dp[i] = Math.max(dp[i], dp[i - cut] + 1);
    }
  }
  return Math.max(dp[n], 0);
}

Time Complexity: O(n)

Space Complexity: O(n)

Saved in this browser only. Private to you.

JavaScript