Minimum Limit of Balls in a Bag

Find the smallest possible maximum bag size after at most maxOperations splits.

binary-search arrays optimization

You are given an array `nums` where `nums[i]` is the number of balls in the i-th bag. You can perform at most `maxOperations` operations. In one operation, you take any bag and split it into two non-empty bags, each containing a positive integer number of balls. The total number of balls is unchanged. Your goal is to minimize the maximum number of balls in any bag after performing at most `maxOperations` operations.

Write a function `minimum_size(nums, maxOperations)` that returns the minimum possible maximum bag size.

For example, if `nums = [9]` and `maxOperations = 2`, you can split the 9-ball bag into [3,6], then split the 6 into [3,3], resulting in [3,3,3] with maximum 3. No smaller maximum is possible because 9 balls must be distributed into at least 3 bags, so the minimum possible maximum is 3.

**Function signature:** `def minimum_size(nums: list[int], maxOperations: int) -> int:`

Constraints

<= len(nums) <= 10^5
<= nums[i] <= 10^9
<= maxOperations <= 10^9
The answer is guaranteed to fit in a 32-bit integer.

Example

>>> minimum_size([9], 2)
3
>>> minimum_size([2,4,8,2], 4)
2
>>> minimum_size([7,17], 2)
7

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about binary searching the answer: if we decide a maximum bag size X, can we check whether it's possible to make all bags ≤ X with at most maxOperations splits?

For a bag with size s, to make it ≤ X, you need to split it into ceil(s / X) pieces, which requires ceil(s / X) - 1 splits.

Use the check function to decide if a given X is feasible, then binary search for the smallest feasible X.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.