Skip to main content
Talentd

Cutting Ribbons - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBinary Search12 min readAsked at: Meta, Google
Practice this problem

Problem Statement

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.

 

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 <= 105
  • 1 <= ribbons[i] <= 105
  • 1 <= 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).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Length EnumerationO(n * m)O(1)Small ribbon lengths or when explaining baseline logic before optimization
Binary Search on AnswerO(n log m)O(1)General case and interview solution when ribbon lengths can be large

Video Solution

CUTTING RIBBONS | PYTHON | LEETCODE # 1891 • Cracking FAANG • 9,248 views views

Watch 6 more video solutions →

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.

Ready to solve this problem?

Practice Cutting Ribbons with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Minimum Number of Rungs

Next

Capacity To Ship Packages Within D Days