Cutting Ribbons

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def maxLength(self, ribbons: List[int], k: int) -> int:
        def is_valid(length: int) -> bool:
            # Check if it's possible to cut ribbons into 'k' pieces of the given length
            return sum(ribbon // length for ribbon in ribbons) >= k

        # The result can be in the range from 1 to the maximum length in ribbons
        left, right = 1, max(ribbons)

        # Apply binary search to find the maximum valid length
        while left <= right:
            mid = (left + right) // 2

            # Check if the current mid length is valid
            if is_valid(mid):
                left = mid + 1
            else:
                right = mid - 1

        # Return the result, or 0 if not possible
        return right if right > 0 else 0