Cutting Ribbons
01 · Problem
You are given an array ribbons where ribbons[i] is the length of the i-th ribbon, and an integer k.
You may cut any ribbon into any number of pieces of positive integer length, or leave it uncut. Leftover scraps may be thrown away.
Return the largest positive integer x such that you can obtain at least k pieces that each have length exactly x. If no positive length allows k pieces, return 0.
02 · Examples
ribbons = [12,8,6], k = 4
6
Length 6 yields 2 + 1 + 1 = 4 pieces. Length 7 yields only 1 + 1 + 0 = 2 pieces.
ribbons = [10,4,7], k = 5
3
Length 3 yields 3 + 1 + 2 = 6 pieces. Length 4 yields only 2 + 1 + 1 = 4 pieces.
ribbons = [3,2,4], k = 10
0
Even length 1 gives only 3 + 2 + 4 = 9 pieces, which is fewer than 10.
03 · Constraints
- 011 <= ribbons.length <= 105
- 021 <= ribbons[i] <= 105
- 031 <= k <= 109
04 · Optimal complexity
- Time
- O(n log(max(ribbons)))
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.