Cutting ribbons

Array Binary Search

53.0% acceptance

Mar 31, 2026

630

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 least k 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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_length(ribbons: Vec<i32>, k: i32) -> i32 {
    let max_len = *ribbons.iter().max().unwrap();
    let mut lo = 1i32;
    let mut hi = max_len;
    let mut ans = 0;
    while lo <= hi {
      let mid = lo + (hi - lo) / 2;
      let count: i64 = ribbons.iter().map(|&r| (r / mid) as i64).sum();
      if count >= k as i64 {
        ans = mid;
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
    ans
  }
}