Welcome to Subscribe On Youtube
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: 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 <= 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)$.

class Solution { public int maxLength(int[] ribbons, int k) { int left = 0, right = 0; for (int x : ribbons) { right = Math.max(right, x); } while (left < right) { int mid = (left + right + 1) >>> 1; int cnt = 0; for (int x : ribbons) { cnt += x / mid; } if (cnt >= k) { left = mid; } else { right = mid  1; } } return left; } }

class Solution { public: int maxLength(vector<int>& ribbons, int k) { int left = 0, right = *max_element(ribbons.begin(), ribbons.end()); while (left < right) { int mid = (left + right + 1) >> 1; int cnt = 0; for (int ribbon : ribbons) { cnt += ribbon / mid; } if (cnt >= k) { left = mid; } else { right = mid  1; } } return left; } };

class Solution: def maxLength(self, ribbons: List[int], k: int) > int: left, right = 0, max(ribbons) while left < right: mid = (left + right + 1) >> 1 cnt = sum(x // mid for x in ribbons) if cnt >= k: left = mid else: right = mid  1 return left

func maxLength(ribbons []int, k int) int { left, right := 0, slices.Max(ribbons) for left < right { mid := (left + right + 1) >> 1 cnt := 0 for _, x := range ribbons { cnt += x / mid } if cnt >= k { left = mid } else { right = mid  1 } } return left }

function maxLength(ribbons: number[], k: number): number { let left = 0; let right = Math.max(...ribbons); while (left < right) { const mid = (left + right + 1) >> 1; let cnt = 0; for (const x of ribbons) { cnt += Math.floor(x / mid); } if (cnt >= k) { left = mid; } else { right = mid  1; } } return left; }

/** * @param {number[]} ribbons * @param {number} k * @return {number} */ var maxLength = function (ribbons, k) { let left = 0; let right = Math.max(...ribbons); while (left < right) { const mid = (left + right + 1) >> 1; let cnt = 0; for (const x of ribbons) { cnt += Math.floor(x / mid); } if (cnt >= k) { left = mid; } else { right = mid  1; } } return left; };

impl Solution { pub fn max_length(ribbons: Vec<i32>, k: i32) > i32 { let mut left = 0i32; let mut right = *ribbons.iter().max().unwrap(); while left < right { let mid = (left + right + 1) / 2; let mut cnt = 0i32; for &entry in ribbons.iter() { cnt += entry / mid; if cnt >= k { break; } } if cnt >= k { left = mid; } else { right = mid  1; } } return left; } }