aboutsummaryrefslogtreecommitdiff
path: root/min_balls_in_bag.py
blob: 07b7ce5c07ebb0dfa3b11fecb648143202f89ddd (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 1760. Minimum Limit of Balls in a Bag
from bisect import bisect_left

"""
given an integer array 'nums' where the i'th bag contains
'nums[i]' balls. also given an integer 'max_operations'.
you can perform the following operation at most 'max_operations'
times; take any bag of balls and divide it into two new bags
with a positive number of balls. the penalty is the maximum
number of balls in a bag. you want to minimise your penalty
after the operations. return the minimum possible penalty.
"""


class Solution(object):
    def minimumSize(self, nums, maxOperations):
        """
        :type nums: List[int]
        :type maxOperations: int
        :rtype: int
        """
        return (
            bisect_left(
                range(1, max(nums) + 1),
                0,
                key=lambda x: maxOperations - sum((k - 1) // x for k in nums),
            )
            + 1
        )


if __name__ == "__main__":
    obj = Solution()
    print(obj.minimumSize(nums=[9], maxOperations=2))
    print(obj.minimumSize(nums=[2, 4, 8, 2], maxOperations=4))