Cutting Ribbons

Medium

Google

5 views

Topics:

ArraysBinary Search

You are given an integer array ribbons, where ribbons[i] is the length of the i^th ribbon, and an integer k. You may cut each ribbon into one or more pieces of any positive integer length, or perform no cuts at all.

For example, if you have a ribbon of length 5, you can cut it into two ribbons of lengths 2 and 3, or two ribbons of lengths 1 and 4, or five ribbons of length 1.

Return the maximum positive integer len such that you can obtain at least k ribbons of length len.

Example 1:

Input: ribbons = [9,7,5], k = 3
Output: 5
Explanation:
- First ribbon can be cut into: 9 / 5 = 1 ribbon of length 5.
- Second ribbon can be cut into: 7 / 5 = 1 ribbon of length 5.
- Third ribbon can be cut into: 5 / 5 = 1 ribbon of length 5.
We can obtain 3 ribbons of length 5.

Example 2:

Input: ribbons = [7,5,9], k = 4
Output: 4
Explanation:
- First ribbon can be cut into: 7 / 4 = 1 ribbon of length 4.
- Second ribbon can be cut into: 5 / 4 = 1 ribbon of length 4.
- Third ribbon can be cut into: 9 / 4 = 2 ribbons of length 4.
We can obtain 4 ribbons of length 4.

Example 3:

Input: ribbons = [5,7,9], k = 2
Output: 7
Explanation:
- First ribbon can be cut into: 5 / 7 = 0 ribbons of length 7.
- Second ribbon can be cut into: 7 / 7 = 1 ribbon of length 7.
- Third ribbon can be cut into: 9 / 7 = 1 ribbon of length 7.
We can obtain 2 ribbons of length 7.

Constraints:

1 <= ribbons.length <= 10⁵
1 <= ribbons[i] <= 10⁵
1 <= k <= 10⁹

Cutting Ribbons

Medium

Google

5 views

Topics:

ArraysBinary Search

You are given an integer array ribbons, where ribbons[i] is the length of the i^th ribbon, and an integer k. You may cut each ribbon into one or more pieces of any positive integer length, or perform no cuts at all.

For example, if you have a ribbon of length 5, you can cut it into two ribbons of lengths 2 and 3, or two ribbons of lengths 1 and 4, or five ribbons of length 1.

Return the maximum positive integer len such that you can obtain at least k ribbons of length len.

Example 1:

Input: ribbons = [9,7,5], k = 3
Output: 5
Explanation:
- First ribbon can be cut into: 9 / 5 = 1 ribbon of length 5.
- Second ribbon can be cut into: 7 / 5 = 1 ribbon of length 5.
- Third ribbon can be cut into: 5 / 5 = 1 ribbon of length 5.
We can obtain 3 ribbons of length 5.

Example 2:

Input: ribbons = [7,5,9], k = 4
Output: 4
Explanation:
- First ribbon can be cut into: 7 / 4 = 1 ribbon of length 4.
- Second ribbon can be cut into: 5 / 4 = 1 ribbon of length 4.
- Third ribbon can be cut into: 9 / 4 = 2 ribbons of length 4.
We can obtain 4 ribbons of length 4.

Example 3:

Input: ribbons = [5,7,9], k = 2
Output: 7
Explanation:
- First ribbon can be cut into: 5 / 7 = 0 ribbons of length 7.
- Second ribbon can be cut into: 7 / 7 = 1 ribbon of length 7.
- Third ribbon can be cut into: 9 / 7 = 1 ribbon of length 7.
We can obtain 2 ribbons of length 7.

Constraints:

1 <= ribbons.length <= 10⁵
1 <= ribbons[i] <= 10⁵
1 <= k <= 10⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the length of the ribbons and the desired number of pieces?
Can the length of any ribbon be zero?
If it's not possible to cut the ribbons into the desired number of pieces, what should I return?
Is the desired number of pieces always a positive integer?
If there are multiple possible maximum lengths that allow cutting the ribbons into at least the desired number of pieces, should I return any valid one, or the absolute maximum?

Brute Force Solution

Approach

To solve the ribbon cutting problem using brute force, we systematically try out every possible length for the cut ribbons. We see if a particular length allows us to cut enough ribbons from the given pieces to satisfy the requirement.

Here's how the algorithm would work step-by-step:

Start by considering the smallest possible length for the ribbons we cut.
Check if we can obtain at least the required number of ribbons by cutting all the provided ribbon pieces with this length.
If we can, we store this length as a possible answer.
If not, we move to the next bigger possible length.
We repeat this process, checking every possible length one by one, until we reach the largest possible ribbon length.
From all the lengths that resulted in enough ribbons, choose the maximum one. That's the answer.

Code Implementation

def cutting_ribbons_brute_force(ribbon_lengths, required_ribbons):
    max_length = 0
    for ribbon_length in ribbon_lengths:
        max_length = max(max_length, ribbon_length)

    longest_possible_length = 0

    # Iterate through all possible ribbon lengths
    for current_length in range(1, max_length + 1):
        number_of_ribbons = 0
        for ribbon_length in ribbon_lengths:

            # Calculate how many ribbons of current_length can be cut
            number_of_ribbons += ribbon_length // current_length

        # If enough ribbons can be cut, update answer
        if number_of_ribbons >= required_ribbons:

            # Store the largest length that yields enough ribbons
            longest_possible_length = current_length

    return longest_possible_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m * n) – Let n be the number of ribbon pieces and m be the maximum length of any ribbon piece. The described brute force approach iterates through all possible ribbon lengths from 1 to m. For each length, it iterates through all n ribbon pieces to determine how many ribbons of that length can be cut from each piece. Therefore, the time complexity is proportional to m (the range of possible ribbon lengths) multiplied by n (the number of ribbon pieces), resulting in O(m * n).

Space Complexity

O(1) – The provided plain English explanation of the brute force approach to the ribbon cutting problem does not explicitly mention the use of any auxiliary data structures that scale with the input size. It iterates through possible lengths and checks conditions, likely storing a single variable to keep track of the maximum length found so far. No additional lists, hash maps, or significant data structures are created, implying constant auxiliary space usage irrespective of the number of ribbon pieces or the required number of ribbons.

Optimal Solution

Approach

To efficiently find the longest ribbon piece we can cut, we'll use a process of guessing a length and then checking if we can make enough pieces of that length. We refine our guess based on whether we could make enough pieces or not, eventually zeroing in on the best possible length.

Here's how the algorithm would work step-by-step:

First, find the shortest and longest ribbon lengths we have to work with. These will be our starting points for our guess range.
Take the middle point of this range as our current guess for the ribbon piece length.
Figure out how many pieces we could create by cutting each ribbon to this length and adding up all the pieces. Discard any partial piece of ribbon remaining after cutting.
If we can make at least the required number of pieces, it means our guess is either correct or too small. Try a longer ribbon length for the next guess.
If we can't make enough pieces, it means our guess is too big. Try a shorter ribbon length for the next guess.
Keep adjusting your guess up or down until the range between your guesses becomes very small. The final guess will be the longest possible ribbon length we can cut to make the required number of pieces.

Code Implementation

def cutting_ribbons(ribbon_lengths, required_pieces):
    shortest_ribbon = 1
    longest_ribbon = max(ribbon_lengths)

    while shortest_ribbon <= longest_ribbon:
        possible_ribbon_length = (shortest_ribbon + longest_ribbon) // 2
        number_of_pieces = 0

        for ribbon_length in ribbon_lengths:
            number_of_pieces += ribbon_length // possible_ribbon_length

        # If enough pieces, increase the possible ribbon length.
        if number_of_pieces >= required_pieces:

            shortest_ribbon = possible_ribbon_length + 1
        # Otherwise, decrease the possible ribbon length.
        else:

            longest_ribbon = possible_ribbon_length - 1

    # Need to return the longest valid length.
    return longest_ribbon

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n * log(m)) – The algorithm performs a binary search to find the optimal ribbon length. The binary search space is defined by the minimum and maximum ribbon lengths, represented by 'm'. Inside the binary search loop, for each guessed ribbon length, we iterate through all 'n' ribbons to calculate the number of pieces we can cut. This 'n' iteration takes O(n) time. Since binary search takes O(log(m)) time, and we perform an O(n) operation inside each binary search step, the overall time complexity is O(n * log(m)).

Space Complexity

O(1) – The algorithm primarily uses a binary search approach to find the optimal ribbon length. It stores a few variables such as the shortest ribbon length, the longest ribbon length, the current guess, and the number of pieces. The number of variables used does not depend on the number of ribbons or the required number of pieces. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Empty ribbons array	Return 0, as no ribbon can be cut.
All ribbon lengths are 0	If k > 0, return 0; if k == 0, return maximum integer value (or appropriate error if undefined).
k is 0	Return the maximum possible length (longest ribbon), or handle it as a special valid case if needed.
k is very large, greater than sum of lengths	The binary search for the length can converge to 0 if the target number of pieces is too large, so handle this scenario returning 0.
Ribbon lengths are very large numbers, leading to integer overflow in the count calculation	Use a data type with a larger range (e.g., long) to store the number of pieces calculated in the count function.
Ribbon lengths contain floating point values.	The problem specified integers, but if floats are permitted then set the correct precision for comparison in the binary search and count functions.
Maximum ribbon length is 1 and k is greater than the number of ribbons	Handle this case by returning 1 if the number of ribbons is greater or equal to k, and 0 if otherwise.
One ribbon length is extremely large and k is 1	If k is 1, then return the maximum ribbon length.