LeetCode 1891 - Cutting Ribbons

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

The problem requires determining the maximum possible length x of ribbons such that, after cutting or keeping the given ribbons in the array ribbons, you can obtain at least k ribbons of length x. Each ribbon can be cut into smaller segments of positive integer length or left as-is, and any leftover pieces that do not fit the target length can be discarded. The input consists of an array of positive integers representing the lengths of the ribbons and a target number of ribbons k. The expected output is a single integer, which is the maximum length x for which it is possible to get at least k ribbons. If no positive integer length allows producing at least k ribbons, the output should be 0.

The constraints indicate that the input array can be large (up to 100,000 elements) and individual ribbon lengths can also be large (up to 100,000). The required number of ribbons k can be as high as one billion. This rules out naive approaches that would iterate over every possible ribbon length because they would be too slow for the largest inputs.

Important edge cases include situations where k is extremely large relative to the total sum of the ribbons, or where the array contains very short ribbons that cannot meet k even if all are cut into the smallest pieces. The problem guarantees all input lengths and k are positive integers, so negative numbers and zeros are not a concern.

Approaches

The brute-force approach would attempt every possible ribbon length from 1 up to the maximum ribbon length in the array, counting how many ribbons of that length can be obtained by summing the integer divisions of each ribbon length by the candidate length. This method works because it explicitly tests all possible lengths, but it is too slow because it would require iterating potentially 100,000 possible lengths for each of the 100,000 ribbons, leading to a worst-case time complexity on the order of 10 billion operations, which is impractical.

The key observation that enables an efficient solution is that the number of ribbons obtainable is a monotonic decreasing function of the ribbon length. That is, as the candidate length increases, the total number of ribbons that can be obtained cannot increase. This property allows using binary search over the range of possible lengths to find the maximum valid length efficiently. Instead of testing every length, we check the midpoint, determine if it produces at least k ribbons, and adjust the search interval accordingly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * max(ribbons))	O(1)	Try every possible length from 1 to max ribbon length, count ribbons
Optimal	O(n * log(max(ribbons)))	O(1)	Binary search over length, checking ribbon counts

Algorithm Walkthrough

Initialize the binary search interval with left = 1 (minimum possible ribbon length) and right = max(ribbons) (maximum ribbon length).
While left <= right, compute the midpoint mid = left + (right - left) // 2. This represents a candidate ribbon length.
Compute the total number of ribbons that can be obtained if each ribbon is cut into pieces of length mid. For a ribbon of length r, the number of pieces is r // mid.
If the total number of ribbons is at least k, it means it is possible to achieve k ribbons of length mid or longer. Record mid as a potential answer and move the search interval to higher lengths: left = mid + 1.
If the total number of ribbons is less than k, it is impossible to achieve k ribbons of this length. Adjust the search interval to shorter lengths: right = mid - 1.
Repeat steps 2-5 until the interval is exhausted. The last recorded valid mid is the maximum possible ribbon length. If no valid length is found, return 0.

Why it works: The binary search relies on the monotonicity property: as the ribbon length increases, the number of pieces decreases. By checking the midpoint at each iteration, we efficiently narrow down the largest possible length that still satisfies the requirement of at least k ribbons.

Python Solution

from typing import List

class Solution:
    def maxLength(self, ribbons: List[int], k: int) -> int:
        left, right = 1, max(ribbons)
        result = 0
        
        while left <= right:
            mid = left + (right - left) // 2
            total_ribbons = sum(ribbon // mid for ribbon in ribbons)
            
            if total_ribbons >= k:
                result = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return result

The Python implementation first determines the search range. The main loop uses binary search to find the maximum feasible length. total_ribbons is calculated using a generator expression that divides each ribbon length by the candidate length mid. If total_ribbons meets or exceeds k, we update result and search the higher half; otherwise, we search the lower half.

Go Solution

func maxLength(ribbons []int, k int) int {
    left, right := 1, 0
    for _, r := range ribbons {
        if r > right {
            right = r
        }
    }
    
    result := 0
    for left <= right {
        mid := left + (right - left) / 2
        total := 0
        for _, r := range ribbons {
            total += r / mid
        }
        
        if total >= k {
            result = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return result
}

The Go implementation is very similar to the Python version. We compute the maximum ribbon length to set the upper bound. A for loop replaces the generator expression to compute the total number of ribbons. Integer division is used naturally in Go, and the search interval is adjusted based on the result.

Worked Examples

Example 1: ribbons = [9,7,5], k = 3

Iteration	left	right	mid	total_ribbons	action
1	1	9	5	3	total >= k, result=5, left=6
2	6	9	7	2	total < k, right=6
3	6	6	6	2	total < k, right=5

Output: 5

Example 2: ribbons = [7,5,9], k = 4

Iteration	left	right	mid	total_ribbons	action
1	1	9	5	4	total >= k, result=5, left=6
2	6	9	7	2	total < k, right=6
3	6	6	6	1	total < k, right=5

Output: 4 (last feasible mid was 4 during adjustments)

Example 3: ribbons = [5,7,9], k = 22

Iteration	left	right	mid	total_ribbons	action
1	1	9	5	4	total < k, right=4
2	1	4	2	10	total < k, right=1
3	1	1	1	21	total < k, right=0

Output: 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * log(max(ribbons)))	Binary search over possible lengths, for each length we iterate through all ribbons
Space	O(1)	Only variables are used for the search interval and totals; no extra structures proportional to n

The algorithm avoids storing all possible ribbon lengths or combinations, which keeps space usage minimal.

Test Cases

# Provided examples
assert Solution().maxLength([9,7,5], 3) == 5  # simple case with exact cut
assert Solution().maxLength([7,5,9], 4) == 4  # multiple small cuts
assert Solution().maxLength([5,7,9], 22) == 0  # impossible to get k ribbons

# Edge cases
assert Solution().maxLength([1], 1) == 1  # smallest ribbon and k
assert Solution().maxLength([1], 2) == 0  # impossible to satisfy k
assert Solution().maxLength([100000]*100000, 1000000000) == 1  # stress test with large numbers
assert Solution().maxLength([1,2,3,4,5], 5) == 1  # small k, multiple lengths
assert Solution().maxLength([1,2,3,4,5], 10) == 1  # small ribbons, k exceeds sum

Test	Why
[9,7,5