LeetCode 1891. Cutting Ribbons

Link : https://leetcode.com/problems/cutting-ribbons

/**
 * LeetCode 1891. Cutting Ribbons
 * Problem: Given an array of ribbon lengths and a target count k, find the maximum length
 * we can cut the ribbons into to get at least k pieces.
 * 
 * Approach: Binary Search
 * 1. The answer must lie between 1 and max(ribbons)
 * 2. For each possible length, check if we can get k pieces
 * 3. Use binary search to find the maximum valid length
 * 
 * Time Complexity: O(n * log(max(ribbons))) where n is the length of ribbons array
 * Space Complexity: O(1) as we only use constant extra space
 */
class CuttingRibbons {
    public int maxLength(int[] ribbons, int k) {
        // Find the maximum ribbon length
        long sum = 0;
        int maxLen = 0;
        for (int ribbon : ribbons) {
            maxLen = Math.max(maxLen, ribbon);
            sum += ribbon;
        }

        // If total possible pieces are less than k, return 0
        if (sum < k) return 0;

        // Binary search for the maximum valid length
        int left = 1, right = maxLen;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (canCut(ribbons, mid, k)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    // Helper function to check if we can cut ribbons into at least k pieces
    // of given length
    private boolean canCut(int[] ribbons, int length, int k) {
        int pieces = 0;
        for (int ribbon : ribbons) {
            pieces += ribbon / length;
            if (pieces >= k) return true;
        }
        return false;
    }

    /**
     * Similar Problems:
     * 1. LC 875: Koko Eating Bananas
     * 2. LC 1011: Capacity To Ship Packages Within D Days
     * 3. LC 410: Split Array Largest Sum
     * 
     * All these problems use binary search on the answer space where:
     * 1. Answer lies in a range
     * 2. Can check if a value is valid
     * 3. Has monotonic property (if x works, all values < x work)
     */
}