Cutting ribbons: longest equal length that yields k pieces

You have pieces of wood (or ribbon) with given lengths and need at least k pieces of one equal length. You may cut pieces but not join them, and leftovers are thrown away. Return the longest integer length that still yields at least k pieces, or 0 if even length 1 is not enough.

Interface

Unless you agree on a different interface with the interviewer, assume:

• max_length(pieces: list[int], k: int) -> int

Example

max_length([9, 7, 5], 3)    ->  5     # 9 -> 1, 7 -> 1, 5 -> 1
max_length([7, 5, 9], 4)    ->  4     # 7 -> 1, 5 -> 1, 9 -> 2
max_length([5, 7, 9], 22)   ->  0     # only 21 units of wood in total

Constraints

• 1 <= len(pieces) <= 10^5, 1 <= pieces[i] <= 10^5, 1 <= k <= 10^9.

Clarifying questions

• Must the length be an integer?
• Do we need at least k pieces or exactly k?
• What is returned when it is impossible?

What a strong answer covers

• The count of pieces sum(p // L) only falls as L grows, so binary search on L over [1, max(pieces)].
• O(n log M) time for M = max(pieces), O(1) space.
• The binary search written to find the last L that works, without an off-by-one, and an early exit when the total length is below k.
• Tests: k = 1 (the answer is the longest piece), impossible cases, all pieces equal.

Follow-ups

• Allow real-valued lengths, with a precision of 10^-6.
• Return the cutting plan as well as the length.
• Each cut has a cost. Minimize the number of cuts for the best length.