Cutting Ribbons

Interview Problem Interview Medium Binary Search on Answer Array Binary Search

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.maxLength(ribbons, k). Cut ribbons into at least k equal integer-length pieces, discarding leftovers. Return the maximum possible piece length, or zero when impossible.

Starter code

class Solution:
    def maxLength(self, ribbons, k):
        pass

Test cases

three-pieces

{
  "args": [
    [
      9,
      7,
      5
    ],
    3
  ]
}

Expected: 5

Wizard outline

Step 1: Initialize Solution.maxLength
Replace the empty starter with the first real state owned by Solution.maxLength. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Pass the Three Pieces case
Complete the readable core algorithm for one representative Interview case. Binary-search the last feasible piece length using sum(ribbon//length).
Step 3: Harden the Four Pieces boundary
Repair the reviewed boundary and pass the complete submission contract. If a length is feasible, every shorter positive length is feasible; feasible lengths form a prefix. The search records feasible candidates and discards only lengths no larger than a confirmed feasible one, so the final record is the maximum feasible length.

Footguns and prerequisites

This is a maximum-feasible search; returning the first infeasible boundary is an off-by-one error.
arrays strings two pointers sliding window

Reviewed references

LeetCode 1891 — Cutting Ribbons

Practice prerequisites

Minimize a Feasible Value(opens in a new tab)
Minimize a Feasible Value isolates left is the first unresolved candidate and right is always a feasible candidate, so the smallest feasible value remains inside [left, right]. That focused state discipline is required when implementing cutting ribbons as a complete Interview Problem.

Recommended approach and implementation

Binary-search positive lengths through the longest ribbon, recording a length when total floor-division pieces reach k and then searching higher.

Why it works: If a length is feasible, every shorter positive length is feasible; feasible lengths form a prefix. The search records feasible candidates and discards only lengths no larger than a confirmed feasible one, so the final record is the maximum feasible length.

class Solution:
    def maxLength(self, ribbons, k):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        left, right = 1, max(ribbons)
        best = 0
        while left <= right:
            length = (left + right) // 2
            pieces = sum(ribbon // length for ribbon in ribbons)
            if pieces >= k:
                best = length
                left = length + 1
            else:
                right = length - 1
        return best

Similar exercises

Koko Eating Bananas(opens in a new tab)