Cutting Ribbons - Leetcode Solution

Problem Statement:

Given a set of n ribbons of different lengths and an integer k, cut the ribbons into k pieces such that the length of each piece is the maximum possible.

Solution:

We are given an array of n ribbons with different lengths. We need to cut them into k pieces in such a way that each piece has maximum length.

To solve this problem, we can use the binary search approach. We will start with the maximum possible length that we can cut each ribbon and then decrease it by binary search until we find the maximum possible length such that we can cut all the ribbons into k pieces.

We define our search space between 0 and the maximum length of the ribbons. We initialize our left pointer to 0 and right pointer to the maximum length of the ribbons. We calculate the mid-point of the left and right pointer, which will be our current ribbon length.

Next, we iterate through the ribbon array and calculate how many pieces we can get if we divide each ribbon by the current length. If the number of pieces is greater than or equal to k, then we update our left pointer to the current length, which means that we can cut the ribbons into k pieces of length greater than or equal to the current length. If the number of pieces is less than k, then we update our right pointer to the current length, which means that we need to cut the ribbons into pieces of length less than the current length.

We repeat the above steps until the difference between the left and right pointer becomes 1. The maximum possible length of the pieces will be the left pointer.

Below is the Python code for this approach:

def cut_ribbons(ribbons, k):

    def count_pieces(length):
        pieces = 0
        for ribbon in ribbons:
            pieces += ribbon // length
        return pieces

    left, right = 0, max(ribbons)
    while left < right - 1:
        mid = (left + right) // 2
        pieces = count_pieces(mid)
        if pieces >= k:
            left = mid
        else:
            right = mid
    return left

Time Complexity: O(n*log(max(ribbons))) Space Complexity: O(1)

1