Coding

Cutting Ribbons

Asked at

Expedia

Google

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

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

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.

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.

Input: ribbons = [10,15,20], k = 5.

1 <= ribbons.length <= 105
1 <= ribbons[i] <= 105
1 <= k <= 109

cpp

class Solution {
public:
   int maxLength(vector<int>& ribbons, int k) {
       // Your code goes here
   }
};

java

class Solution {
    public int maxLength(int[] ribbons, int k) {
        // Your code goes here
    }
}

python

class Solution:
    def maxLength(self, ribbons, k):
        # Your code goes here

javascript

class Solution {
    maxLength(ribbons, k) {
        // Your code goes here
    }
}

csharp

public class Solution
{
    public int maxLength(int[] ribbons, int k)
    {
        // Your code goes here
    }
}

func maxLength(ribbons []int, k int) int {
    // Your code goes here
}

Stuck? Show a way to structure it+

01Binary-search a candidate piece length between 1 and the maximum ribbon length.
02For a candidate x, sum `length / x` across ribbons.
03It is feasible when the sum is at least k.
04Keep the largest feasible length and return 0 if none is feasible.

Reference answer

For a fixed piece length x, each ribbon of length r yields floor(r/x) pieces. Thus feasibility is monotonic: if x works, every smaller positive length works. Binary-search the largest feasible x in [1, max(ribbons)]; during each check, accumulate pieces and stop early once the count reaches k. If even length 1 is infeasible, return 0. The time is O(n log M), where M is the largest ribbon length, and space is O(1). Use a wide count because the sum of produced pieces can exceed 32-bit range.

Then expect these follow-ups

How would you find the minimum speed to finish jobs by a deadline?
Tests: pattern recognition
Why is discarding leftovers allowed in the feasibility check?
Tests: problem modeling

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question