What Is Cable Cutting?
Given a few cables of all different lengths, you want to cut them all into equal-length pieces to make at least K pieces — and the question is: "What is the maximum length of a single piece?"
The key idea is that we binary-search the answer (the piece length) itself. Unlike ordinary binary search that looks up a value in an array, here we halve the "range of possible lengths" to home in on the answer. This technique is called parametric search.
Why Does Binary Search Work?
If the piece length is L, the number of pieces we can make is:
count(L) = ⌊cable₁ / L⌋ + ⌊cable₂ / L⌋ + ... + ⌊cableₙ / L⌋- •Shrinking L never decreases the count → monotonicity
- •So there is a single boundary of L where "count ≥ K" holds
- •Find that boundary with binary search, and you're done
This monotonicity is the prerequisite for parametric search. The core insight is turning an optimization problem ("what is the max length?") into a decision problem ("can this length make K pieces?").
How It Works
Step 1. Set the search range: lo = 1, hi = the longest cable length.
Step 2. Take mid = (lo + hi) / 2 as the candidate piece length.
Step 3. Count how many pieces you can make at mid (the decision function).
- •count ≥ K → Possible! Save it as a candidate and
lo = mid + 1(try longer) - •count < K → Not enough!
hi = mid - 1(cut shorter to make more)
Step 4. Repeat until lo > hi; the last saved candidate is the answer.
Walking Through the Example
For cables [57, 42, 36, 20] and required count K = 3:
| Piece length L | Count | Result |
|---|---|---|
| 29 | 1+1+1+0 = 3 | OK → lo=30 |
| 43 | 1+0+0+0 = 1 | Short → hi=42 |
| 36 | 1+1+1+0 = 3 | OK → lo=37 (candidate) |
| 39 | 1+1+0+0 = 2 | Short → hi=38 |
| 37 | 1+1+0+0 = 2 | Short → hi=36 |
lo(37) > hi(36), so we stop. The answer is 36. At L=37 we could make only 2 pieces, so it was impossible.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(N log L) |
| Space | O(1) |
We try the candidate length about log L times, summing over N cables each time, giving O(N log L). Even with cable lengths of a billion, about 30 iterations suffice.
Common Mistakes
- •Starting lo at 0: You cannot divide by length 0. Always start at
lo = 1. - •Count overflow: With many long cables, the count can be huge. Accumulate in a 64-bit integer (long).
- •Wrong boundary updates: Mixing up "if possible, go longer (lo=mid+1)" and "if short, go shorter (hi=mid-1)" leads to infinite loops or wrong answers.
See It in Action on AlgoNote
Watch how the piece length narrows step by step in Cable Cutting, and how many pieces each length yields, with AlgoNote's interactive visualization.