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 length 1,
Cut it into two ribbons of length 2,
Cut it into one ribbon of length 2 and two ribbons of length 1, or
Cut it into four ribbons of length 1.
Your task is to determine the maximum length of ribbon, x, that allows you to cut at leastk ribbons, each of length x. You can discard any leftover ribbon from the cuts. If it is impossible to cut k ribbons of the same length, return 0.
Input: ribbons =[9,7,5], k =3Output: 5Explanation:
- 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:
1
2
3
4
5
6
7
Input: ribbons =[7,5,9], k =4Output: 4Explanation:
- 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:
1
2
3
Input: ribbons =[5,7,9], k =22Output: 0Explanation: You cannot obtain k ribbons of the same positive integer length.
The key idea is to use binary search to find the maximum possible length x such that we can cut at least k ribbons of length x. For a given length, we can check in linear time how many ribbons of that length can be made from the input.
classSolution {
public:int maxLength(vector<int>& ribbons, int k) {
int l =1, r =*max_element(ribbons.begin(), ribbons.end()), ans =0;
while (l <= r) {
int m = l + (r - l) /2, cnt =0;
for (int x : ribbons) cnt += x / m;
if (cnt >= k) {
ans = m;
l = m +1;
} else {
r = m -1;
}
}
return ans;
}
};
funcmaxLength(ribbons []int, kint) int {
l, r, ans:=1, 0, 0for_, x:=rangeribbons {
ifx > r {
r = x }
}
forl<=r {
m:=l+ (r-l)/2cnt:=0for_, x:=rangeribbons {
cnt+=x/m }
ifcnt>=k {
ans = ml = m+1 } else {
r = m-1 }
}
returnans}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution {
publicintmaxLength(int[] ribbons, int k) {
int l = 1, r = 0, ans = 0;
for (int x : ribbons) r = Math.max(r, x);
while (l <= r) {
int m = l + (r - l) / 2, cnt = 0;
for (int x : ribbons) cnt += x / m;
if (cnt >= k) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classSolution {
funmaxLength(ribbons: IntArray, k: Int): Int {
var l = 1var r = ribbons.maxOrNull() ?:0var ans = 0while (l <= r) {
val m = l + (r - l) / 2var cnt = 0for (x in ribbons) cnt += x / m
if (cnt >= k) {
ans = m
l = m + 1 } else {
r = m - 1 }
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
classSolution:
defmaxLength(self, ribbons: list[int], k: int) -> int:
l, r, ans =1, max(ribbons), 0while l <= r:
m = (l + r) //2 cnt = sum(x // m for x in ribbons)
if cnt >= k:
ans = m
l = m +1else:
r = m -1return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
impl Solution {
pubfnmax_length(ribbons: Vec<i32>, k: i32) -> i32 {
let (mut l, mut r, mut ans) = (1, *ribbons.iter().max().unwrap(), 0);
while l <= r {
let m = l + (r - l) /2;
let cnt: i32= ribbons.iter().map(|&x| x / m).sum();
if cnt >= k {
ans = m;
l = m +1;
} else {
r = m -1;
}
}
ans
}
}