Problem statement

https://binarysearch.com/problems/Cut-Ribbons-of-Same-Length/

Solution

Equal to Leetcode 1891 Cutting Ribbons, but we have one more edgecase here.

Complexity

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

Code

class Solution:
    def solve(self, R, k):
        if sum(R) < k: return -1
        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