1891. Cutting Ribbons π
Description
You are given an integer array ribbons
, where ribbons[i]
represents the length of the ith
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:- Keep the ribbon of length
4
, - Cut it into one ribbon of length
3
and one ribbon of length1
, - Cut it into two ribbons of length
2
, - Cut it into one ribbon of length
2
and two ribbons of length1
, or - Cut it into four ribbons of length
1
.
- Keep the ribbon of length
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 <= 105
1 <= ribbons[i] <= 105
1 <= k <= 109
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 $x-1$. 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 $mid-1$.
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)$.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|