Maximize The Cut Segments | Practice | Problems

Given a rod of length n and three segment lengths x, y, and z, maximize the number of segments the rod can be cut into such that each segment has length x, y, or z. If the rod cannot be completely cut into valid segments, return 0.

Example 1:

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

Example 2:

Input: n = 5, x = 5, y = 3, z = 2
Output: 2

Sample Input

—

Sample Output

—

Constraints

1 <= N <= 10^4
1 <= x, y, z <= N

Test Cases

Case 1

Args: [4,2,1,1] Expected: 4

Topics

Dynamic Programming Memoization

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

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.