366. Ribbon Cutter with Blade Loss
A craft shop owns several ribbons, where ribbons[i] is the length in whole centimetres of the i-th ribbon. A customer needs at least k pieces that all have the same whole-number length, and the shop wants those pieces to be as long as possible.
The cutting blade is thick: every cut destroys exactly 1 cm of ribbon, and a ribbon of length r therefore gives m pieces of length L only if m * L + (m - 1) <= r. Return the largest length L that lets the shop collect at least k pieces, or 0 if even pieces of length 1 are not enough. Leftover ribbon is simply thrown away.
Example 1
- Input:
- ribbons = [9,7,5], k = 4
- Output:
- 4
- Explanation:
With L = 4, the ribbons give 2, 1 and 1 pieces (a 9 cm ribbon holds 4 + 1 + 4), which is 4 pieces. With L = 5 they give only 1 + 1 + 1 = 3, so the answer is 4.
Example 2
- Input:
- ribbons = [3,3], k = 5
- Output:
- 0
- Explanation:
Pieces of length 1 give 2 per ribbon (1 + 1 + 1 = 3 cm), so only 4 pieces in total. That is less than 5, so the answer is 0.
Constraints
1 ≤ ribbons.length ≤ 105
1 ≤ ribbons[i] ≤ 107
1 ≤ k ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log M), where M is the longest ribbon
- Space
- O(1)