Maximize The Cut Segments

Problem Statement

Given an integer n (the length of a line segment) and three values x, y, z, find the maximum number of segments the line can be cut into, where each segment has length x, y, or z.

Example:

• Input: n = 4, x = 2, y = 1, z = 1
• Output: 4 (cut into four segments of length 1, 1, 1, 1 — or 2, 1, 1)

Noob-Friendly Explanation

Imagine you have a rope that is 4 meters long. You can cut it into pieces of 2m, 1m, or 1m. You want to cut it into the maximum number of pieces. If you cut into all 1m pieces, you get 4 pieces! That's the most you can get. The problem asks: given a length and three allowed piece sizes, what's the most pieces you can make?

Approach 1: Brute Force (Recursion)

Intuition

At each step, try cutting a piece of length x, y, or z. Recurse on the remaining length. Return the maximum number of cuts.

Algorithm

1. If n == 0, return 0 (no more to cut)
2. If n < 0, return -1 (invalid cut)
3. Try cutting x, y, and z; pick the maximum

public class Solution {
    public int maximizeCuts(int n, int x, int y, int z) {
        if (n == 0) return 0;
        if (n < 0) return -1;

        int cutX = maximizeCuts(n - x, x, y, z);
        int cutY = maximizeCuts(n - y, x, y, z);
        int cutZ = maximizeCuts(n - z, x, y, z);

        int maxVal = Math.max(cutX, Math.max(cutY, cutZ));

        // If none of the cuts worked, this path is invalid
        if (maxVal == -1) return -1;

        return maxVal + 1;
    }
}

Complexity Analysis

• Time Complexity: O(3^n) - Each call branches into 3 sub-calls
• Space Complexity: O(n) - Recursion stack depth

Approach 2: Optimal (Bottom-Up DP)

Intuition

Build an array where dp[i] stores the maximum number of segments for length i. For each length, try all three cut sizes and pick the best.

Algorithm

1. Create array dp[n+1], initialize all to -1 except dp[0] = 0
2. For each length from 1 to n:
   • If cutting x is valid and dp[i-x] != -1, update dp[i]
   • Same for y and z
3. If dp[n] is -1, return 0 (can't cut); otherwise return dp[n]

public class Solution {
    public int maximizeCuts(int n, int x, int y, int z) {
        int[] dp = new int[n + 1];
        java.util.Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            if (i >= x && dp[i - x] != -1) {
                dp[i] = Math.max(dp[i], dp[i - x] + 1);
            }
            if (i >= y && dp[i - y] != -1) {
                dp[i] = Math.max(dp[i], dp[i - y] + 1);
            }
            if (i >= z && dp[i - z] != -1) {
                dp[i] = Math.max(dp[i], dp[i - z] + 1);
            }
        }

        return dp[n] == -1 ? 0 : dp[n];
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass through lengths 1 to n, constant work per length
• Space Complexity: O(n) - Array of size n + 1