Cutting Ribbons

Problem

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.

Examples

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

Solution

Method 1 – Binary Search on Answer

Intuition

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.

Approach

1. Set the search range for x from 1 to the maximum ribbon length.
2. For each candidate length mid, count how many ribbons of length mid can be made from all ribbons.
3. If the count is at least k, try a longer length (move right); otherwise, try a shorter length (move left).
4. The answer is the largest length for which at least k ribbons can be made.

Code

C++

class Solution {
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;
    }
};

Go

func maxLength(ribbons []int, k int) int {
    l, r, ans := 1, 0, 0
    for _, x := range ribbons {
        if x > r {
            r = x
        }
    }
    for l <= r {
        m := l + (r-l)/2
        cnt := 0
        for _, x := range ribbons {
            cnt += x / m
        }
        if cnt >= k {
            ans = m
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return ans
}

Java

class Solution {
    public int maxLength(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;
    }
}

Kotlin

class Solution {
    fun maxLength(ribbons: IntArray, k: Int): Int {
        var l = 1
        var r = ribbons.maxOrNull() ?: 0
        var ans = 0
        while (l <= r) {
            val m = l + (r - l) / 2
            var cnt = 0
            for (x in ribbons) cnt += x / m
            if (cnt >= k) {
                ans = m
                l = m + 1
            } else {
                r = m - 1
            }
        }
        return ans
    }
}

Python

class Solution:
    def maxLength(self, ribbons: list[int], k: int) -> int:
        l, r, ans = 1, max(ribbons), 0
        while l <= r:
            m = (l + r) // 2
            cnt = sum(x // m for x in ribbons)
            if cnt >= k:
                ans = m
                l = m + 1
            else:
                r = m - 1
        return ans

Rust

impl Solution {
    pub fn max_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
    }
}

TypeScript

class Solution {
    maxLength(ribbons: number[], k: number): number {
        let l = 1, r = Math.max(...ribbons), ans = 0;
        while (l <= r) {
            const m = Math.floor((l + r) / 2);
            let cnt = 0;
            for (const x of ribbons) cnt += Math.floor(x / m);
            if (cnt >= k) {
                ans = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n log M), where n is the number of ribbons and M is the max ribbon length, due to binary search and linear scan per check.
• 🧺 Space complexity: O(1), as only a few variables are used.