Problem statement

https://binarysearch.com/problems/Maximum-of-the-Smallest-Chunk/

Solution

Equal to Leetcode 1231 Divide Chocolate, but change K + 1 to K.

Complexity

Time complexity is O(n*log(Q)), where Q = sum(nums)//(K+1) + 1. Space complexit is O(n).

Code

class Solution:
    def solve(self, nums, K):
        def check(Q):
            acc, ans = 0, 0
            for num in nums + [0]:
                if acc < Q:
                    acc += num
                else:
                    acc = num
                    ans += 1
            return ans >= K

        beg, end = 1, sum(nums)//K + 1
        while beg + 1 < end:
            mid = (beg + end)//2
            if not check(mid):
                end = mid
            else:
                beg = mid
        
        return beg