Minimum Limit of Balls in a Bag — Medium Problem & Solution

Problem statement

Bag i holds nums[i] balls. One operation takes a bag and splits it into two bags with a positive number of balls each.

The penalty is the largest number of balls in any bag. Return the minimum possible penalty after at most maxOperations operations.

Example 1

Input: nums = [9], maxOperations = 2
Output: 3
Explanation: 9 → 6 and 3 → 3, 3 and 3.

Example 2

Input: nums = [2,4,8,2], maxOperations = 4
Output: 2

Example 3

Input: nums = [7,17], maxOperations = 2
Output: 7

Constraints

• 1 <= nums.length <= 100000
• 1 <= maxOperations, nums[i] <= 1000000000

How to solve Minimum Limit of Balls in a Bag

Binary search the penalty. For a target L, each bag's cost is independent: a bag of x balls needs ceil(x / L) pieces, and every split adds one piece, so it costs ceil(x / L) - 1 operations.

Approach

1. Search L over [1, max(nums)].
2. can(L): sum floor((x - 1) / L) over the bags, which equals ceil(x / L) - 1 for positive x.
3. Return the smallest L whose total is at most maxOperations.

Why it works

Splitting is unconstrained in how it divides a bag, so ceil(x / L) equal-ish pieces is always reachable and is the fewest pieces with every piece at most L. A tree with p leaves takes p - 1 splits, giving the cost formula. Raising L weakly lowers every bag's cost, so the total is non-increasing — the monotonicity the search needs.

Complexity

• Time — O(n log M) where M is the largest bag
• Space — O(1)

Pitfalls

• ceil(x / L) computed in floating point rounds wrongly for large values — use floor((x - 1) / L) instead.
• L starts at 1, not 0 — a bag must keep a positive count.
• The total operation count reaches 10^5 · 10^9, so accumulate in 64-bit or short-circuit once the budget is exceeded.

Reference solution

Python

from typing import List

def minimumSize(nums: List[int], maxOperations: int) -> int:
    lo, hi = 1, max(nums)

    def can(limit: int) -> bool:
        ops = 0
        for x in nums:
            ops += (x - 1) // limit
            if ops > maxOperations:
                return False
        return True

    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

JavaScript

var minimumSize = function(nums, maxOperations) {
    var lo = 1, hi = nums[0], i;
    for (i = 1; i < nums.length; i++) if (nums[i] > hi) hi = nums[i];
    var can = function(limit) {
        var ops = 0;
        for (var j = 0; j < nums.length; j++) {
            ops += Math.floor((nums[j] - 1) / limit);
            if (ops > maxOperations) return false;
        }
        return true;
    };
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (can(mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium