Problem statement

https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/

Solution

The idea of this problem is to use binary search, where we ask question: given mid restriction for each shop, how many shops we need to distribute all goods? For example if we have Q = [6, 11] and mid = 6, then we need 3 shops: [6], [6, 5]. If we have mid = 3, we need 6 shops: [3, 3], [3, 3, 3, 2]. What we need to find is the smallest mid, such that we have <= n shops needed.

Complexity

It is O(n * log W), where W = sum(Q).

Code

class Solution:
    def minimizedMaximum(self, n, Q):
        beg, end = 0, max(Q)
        
        while beg + 1 < end:
            mid = (beg + end)//2
            if sum(ceil(i/mid) for i in Q) <= n:
                end = mid
            else:
                beg = mid
        
        return end