1891. Cutting Ribbons
Description
You are given an integer array ribbons
, where ribbons[i]
represents the length of the i^{th}
ribbon, and an integer k
. You may cut any of the ribbons into any number of segments of positive integer lengths, or perform no cuts at all.
 For example, if you have a ribbon of length
4
, you can:<ul> <li>Keep the ribbon of length <code>4</code>,</li> <li>Cut it into one ribbon of length <code>3</code> and one ribbon of length <code>1</code>,</li> <li>Cut it into two ribbons of length <code>2</code>,</li> <li>Cut it into one ribbon of length <code>2</code> and two ribbons of length <code>1</code>, or</li> <li>Cut it into four ribbons of length <code>1</code>.</li> </ul> </li>
Your goal is to obtain k
ribbons of all the same positive integer length. You are allowed to throw away any excess ribbon as a result of cutting.
Return the maximum possible positive integer length that you can obtain k
ribbons of, or 0
if you cannot obtain k
ribbons of the same length.
Example 1:
Input: ribbons = [9,7,5], k = 3 Output: 5 Explanation:  Cut the first ribbon to two ribbons, one of length 5 and one of length 4.  Cut the second ribbon to two ribbons, one of length 5 and one of length 2.  Keep the third ribbon as it is. Now you have 3 ribbons of length 5.
Example 2:
Input: ribbons = [7,5,9], k = 4 Output: 4 Explanation:  Cut the first ribbon to two ribbons, one of length 4 and one of length 3.  Cut the second ribbon to two ribbons, one of length 4 and one of length 1.  Cut the third ribbon to three ribbons, two of length 4 and one of length 1. Now you have 4 ribbons of length 4.
Example 3:
Input: ribbons = [5,7,9], k = 22 Output: 0 Explanation: You cannot obtain k ribbons of the same positive integer length.
Constraints:
1 <= ribbons.length <= 10^{5}
1 <= ribbons[i] <= 10^{5}
1 <= k <= 10^{9}
Solutions
Solution 1: Binary Search
We observe that if we can obtain $k$ ropes of length $x$, then we can also obtain $k$ ropes of length $x1$. This implies that there is a monotonicity property, and we can use binary search to find the maximum length $x$ such that we can obtain $k$ ropes of length $x$.
We define the left boundary of the binary search as $left=0$, the right boundary as $right=\max(ribbons)$, and the middle value as $mid=(left+right+1)/2$. We then calculate the number of ropes we can obtain with length $mid$, denoted as $cnt$. If $cnt \geq k$, it means we can obtain $k$ ropes of length $mid$, so we update $left$ to $mid$. Otherwise, we update $right$ to $mid1$.
Finally, we return $left$ as the maximum length of the ropes we can obtain.
The time complexity is $O(n \times \log M)$, where $n$ and $M$ are the number of ropes and the maximum length of the ropes, respectively. The space complexity is $O(1)$.













