NeetCode #296LC-1891MediumBinary Search
← Back to All Problems#296 · #1891 · Cutting Ribbons(割绳子)
📌 Problem Statement & Constraints
You are given an array
ribbons where ribbons[i] is the length of the i-th ribbon, and an integer k. You may cut each ribbon into pieces of equal integer length; leftover material is discarded. Return the maximum possible piece length so that you obtain at least k pieces, or 0 if impossible. Constraints: 1 <= ribbons.length <= 10^5, 1 <= ribbons[i] <= 10^5, 1 <= k <= 10^9.💡 Core Algorithmic Approaches
- Binary search on the piece length
L: "can we obtain at leastkpieces of lengthL" is monotone. - For a given
L, the number of pieces issum(ribbon // L). - The upper bound is
max(ribbons), since a piece cannot exceed the longest ribbon. - If the total length is less than
k, the answer is 0 -- check this before the search to avoid an off-by-one atL = 1.
💻 Benchmark Python3 Implementation
class Solution:
def maxLength(self, ribbons: List[int], k: int) -> int:
if sum(ribbons) < k:
return 0 # cannot even make k pieces of length 1
lo, hi = 1, max(ribbons)
while lo < hi:
mid = (lo + hi + 1) // 2 # upper-biased: maximise
pieces = sum(r // mid for r in ribbons)
if pieces >= k:
lo = mid # feasible -> try longer
else:
hi = mid - 1
return lo⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log(max(ribbons))): each feasibility check is O(n).
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the feasibility guard: without it, the binary search would return 1 even when fewer than
kpieces of length 1 are available. - Using the lower-biased midpoint with
lo = mid: infinite loop. - Concatenating leftovers from different ribbons: the pieces must come from a single ribbon, so leftovers cannot be combined.
- Using floating-point division: integer division is exact and appropriate.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.