Problem statement

https://leetcode.com/problems/cutting-ribbons/

Solution

The idea is to use binary search: as question: can we get k ribbons of length mid. I think I saw exaclty the same problem on leetcode in different formulation.

Complexity

Time complexity is O(n log n), space is O(1).

Code

class Solution:
    def maxLength(self, R, k):
        beg, end = 0, max(R) + 1
        while beg + 1 < end:
            mid = (beg + end)//2
            if sum(i//mid for i in R) >= k:
                beg = mid
            else:
                end = mid
        
        return beg