Minimum Limit of Balls in a Bag

Problem Id: 1760 Difficulty: Medium Tag: Binary Search Tag: Heap


Intuition

Let assume that a bag has x bags, and if we want to operate on it so that the maximum number of balls is k. Since we can decide the number of balls for each operation, the minimum number of operations is ceil(x / k) - 1.

For example, if x = 9, k = 3, then the number of operations is ceil(x / k) - 1 => ceil(9 / 3) - 1 => 2. And if x = 9 and k = 4, number of operations is ceil(9 / 4) - 1 => 2.

For each k, to calculate the number of operations for all bags to become less than k, the time complexity is O(n).

So we can use binary search here to find a k so that number of operations for k is less than or equal to maxOperations while number of operations for k + 1 is greater than maxOperations.

The total time complexity is O(nums.length * log(maxOperations)).

Solution


import math


class Solution:
    def minimumSize(self, nums, maxOperations):
        low = 1
        high = 10 ** 9 + 1
        if self._minOperations(nums, low) <= maxOperations:
            return low

        while high - low > 1:
            mid = (high + low) // 2
            operations = self._minOperations(nums, mid)
            if operations > maxOperations:
                low = mid
            else:
                high = mid
        return high


    def _minOperations(self, nums, k):
        return sum([math.ceil(num / k) - 1 for num in nums])