Cutting Ribbons — Binary Search on Answer Length Guide

Problem Statement#

Given an array ribbons and an integer k, return the maximum integer length m such that you can cut at least k ribbons of length m from the input ribbons. Return 0 if impossible.

Constraints:

• 1 <= ribbons.length <= 10^5
• 1 <= ribbons[i] <= 10^5
• 1 <= k <= 10^9

Input:  ribbons = [9, 7, 5], k = 3
Output: 5

Input:  ribbons = [7, 5, 9], k = 22
Output: 0

Why This Problem Matters#

LeetCode 1891 is a hard binary search interview problem at Amazon and Google because it stress-tests the maximize variant of search-on-answer. Most candidates know how to minimize a feasible value (e.g. ship-within-D-days). Very few can write the maximize variant cleanly because it requires the upper-mid mid = lo + (hi - lo + 1) // 2 to avoid infinite loops.

The problem also forces correct large-domain reasoning. With k up to 10^9 and ribbon lengths up to 10^5, the answer space is wide and naive linear search times out. Binary search collapses it to O(n log max) — a clean FAANG O(log n) win.

If you can write the maximize template once and articulate why upper-mid is needed, you handle a whole family of problems including capacity allocation, magnetic force, and cake division.

The Core Insight#

For a candidate length m, a single ribbon of length r produces r // m pieces. Sum across the array. The predicate "can we cut at least k pieces of length m" is monotone: if m works, every shorter length also works. We binary search the largest m that satisfies the predicate.

Use upper-mid arithmetic so the loop converges when lo + 1 == hi.

Visual Dry Run#

Input ribbons = [9, 7, 5], k = 4. Range [1, 9].

Loop ends with lo = hi = 4. Answer: 4.

Solution (Optimal)#

class Solution:
    def maxLength(self, ribbons, k):
        def feasible(m):
            return sum(r // m for r in ribbons) >= k
 
        lo, hi = 1, max(ribbons)
        while lo < hi:
            mid = lo + (hi - lo + 1) // 2
            if feasible(mid):
                lo = mid
            else:
                hi = mid - 1
        return lo if feasible(lo) else 0

var maxLength = function(ribbons, k) {
    const feasible = (m) => {
        let cnt = 0;
        for (const r of ribbons) cnt += Math.floor(r / m);
        return cnt >= k;
    };
 
    let lo = 1, hi = Math.max(...ribbons);
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo + 1) / 2);
        if (feasible(mid)) lo = mid;
        else hi = mid - 1;
    }
    return feasible(lo) ? lo : 0;
};

Time: O(n log max) — n elements times log of max ribbon length. Space: O(1) — only counters.

Common Mistakes#

• Using mid = lo + (hi - lo) // 2 (lower-mid) and infinite-looping at lo + 1 == hi.
• Not handling the impossible case when even length-1 cannot reach k pieces.
• Setting hi = sum(ribbons) // k as the upper bound (works but unnecessarily wide).
• Iterating linearly over candidate lengths and timing out on 10^5-sized inputs.
• Forgetting that m must be a positive integer; using doubles introduces precision bugs.

Interview Tips#

• Always say "binary search on the answer" and identify the monotone predicate.
• Justify upper-mid out loud — it is the most common bug in the maximize variant.
• Ask about constraints first; large k invites the search rather than greedy.

Follow-up Questions#

• What if pieces could be combined from multiple ribbons? Different problem — knapsack-like.
• Generalize to fractional lengths? Use floating point with tolerance.
• Minimize the number of cuts to produce k pieces of length m? Greedy and counting.
• Solve LC 875 Koko Eating Bananas as a similar template — it is the minimize variant.
• What if k were astronomically large like 10^18? Same algorithm, watch overflow.

Key Takeaways#

• LC 1891 is the canonical maximize-the-answer binary search.
• Upper-mid lo + (hi - lo + 1) // 2 is mandatory in the maximize variant.
• Predicate sum(r // m) >= k is monotone in m.
• Time complexity is O(n log max).
• Always verify feasibility after the loop in case no m >= 1 works.
• The same template solves capacity, magnetic force, and similar problems.
• Handle large k and overflow by using 64-bit accumulators.