Cutting Ribbons solution and explanation
Google
6 more videos on this problem
CUTTING RIBBONS | PYTHON | LEETCODE # 1891Cracking FAANG · 22:43 · 9K views
Leetcode 1891. Cutting RibbonsUnofficial Sendoh · 10:05 · 1K views
Leetcode 1891DailyLeetcode · 8:06 · 293 views
1891. Cutting Ribbons - Week 2/5 Leetcode December ChallengeProgramming Live with Larry · 6:08 · 222 views
1891. Cutting RibbonsJust Coding, with Jie · 8:25 · 187 views
How to solve the Cutting Wood Coding Problem (inspired by Cutting Ribbons LeetCode #1891)vboskovic · 48:04 · 31 views
LeetCode 1891: Cutting RibbonsAlitaCode · 26:05 · 17 views
The 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
3and one ribbon of length1, - Cut it into two ribbons of length
2, - Cut it into one ribbon of length
2and two ribbons of length1, or - Cut it into four ribbons of length
1.
- Keep the ribbon of length
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.
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 <= 1051 <= ribbons[i] <= 1051 <= k <= 109
Approach overview
Problem Overview: You are given an array where each value represents the length of a ribbon. The task is to cut these ribbons into smaller pieces so that you obtain at least k ribbons of equal length. The goal is to maximize that length.
Approach 1: Brute Force Length Enumeration (Time: O(n * m), Space: O(1))
The simplest idea is to try every possible ribbon length from 1 up to the maximum ribbon length m. For each candidate length L, iterate through the array and count how many pieces you can produce using ribbon // L. If the total count is at least k, the length is feasible. Track the largest valid length during the scan. This works because cutting is independent for each ribbon, so the number of pieces is just integer division. The downside is performance: when the maximum ribbon length is large, iterating through all possible lengths makes the algorithm O(n * m), which becomes too slow for large inputs.
Approach 2: Binary Search on Ribbon Length (Time: O(n log m), Space: O(1))
The key observation: if a length L works (you can make at least k pieces), then every length smaller than L will also work. If L does not work, any larger length will also fail. This monotonic property allows a binary search over the answer space.
Search between 1 and max(ribbons). For a midpoint length mid, compute how many pieces can be formed by summing ribbon // mid for every element in the array. If the count is at least k, the length is feasible, so move the search to the right half to try a larger piece. Otherwise move left because the length is too large. The check itself is a linear scan, making each binary search step O(n). Since the search range halves each time, the overall complexity becomes O(n log m), where m is the maximum ribbon length.
This technique is often called binary search on the answer. Instead of searching indices, you search the space of possible results and validate each candidate using a greedy counting step.
Recommended for interviews: The expected solution is binary search on the ribbon length. Interviewers want to see that you recognize the monotonic feasibility condition and convert the optimization problem into a search problem. Mentioning the brute force approach first shows understanding of the problem space, but implementing the binary search optimization demonstrates stronger algorithmic thinking and reduces the complexity from O(n * m) to O(n log m).
Solution
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).
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 leftclass 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;
}
};/**
* @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;
};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;
}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
}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;
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Length Enumeration | O(n * m) | O(1) | Small ribbon lengths or when explaining baseline logic before optimization |
| Binary Search on Answer | O(n log m) | O(1) | General case and interview solution when ribbon lengths can be large |
Frequently asked questions
Is Cutting Ribbons easy or hard?
Cutting Ribbons is rated Medium difficulty. The challenge is recognizing that the optimal ribbon length forms a monotonic search space. Once you identify the binary search on answer pattern, the implementation becomes straightforward.
Cutting Ribbons Python/Java solution
The typical implementation performs binary search between 1 and max(ribbons). For each midpoint length, iterate through the array and accumulate ribbon // mid to count pieces. FleetCode provides complete implementations in Python, Java, C++, Go, TypeScript, Rust, and JavaScript.
How to solve Cutting Ribbons in O(n)?
An exact O(n) solution is not possible because the algorithm must determine the optimal ribbon length within a numeric range. The best practical approach is binary search on the answer, which runs in O(n log m). Each feasibility check counts pieces using integer division across the array.
What is the best approach for Cutting Ribbons?
Binary search on the ribbon length is the optimal approach. The feasibility of a length is monotonic: if length L can produce at least k pieces, all smaller lengths will also work. This allows searching the range [1, max(ribbons)] with binary search while checking feasibility in O(n). The overall complexity becomes O(n log m).
Is Cutting Ribbons asked at Google/Amazon/Meta?
Cutting Ribbons represents a common interview pattern called binary search on the answer. Variants of this pattern appear frequently in interviews at companies like Google, Amazon, and Meta because they test understanding of monotonic conditions and efficient search strategies.
What data structure is used in Cutting Ribbons?
The problem mainly uses an array to store ribbon lengths and applies binary search on the possible answer range. During each check, a simple greedy counting step computes how many pieces can be produced using integer division.
What is the time complexity of Cutting Ribbons?
The optimal solution runs in O(n log m) time, where n is the number of ribbons and m is the maximum ribbon length. Each binary search step scans the array to count how many pieces can be produced, which costs O(n). The search space halves each iteration, giving the log m factor.