Minimum Limit of Balls in a Bag

medium binary search

Problem

You have bags of balls: nums[i] is the size of bag i. You may perform at most maxOperations operations, each taking one bag and splitting it into two new bags with positive sizes that sum to the original. Your penalty is the size of the largest bag left at the end — make that penalty as small as possible.

Rather than choosing splits directly, binary search the answer: for a candidate cap m, a bag of x balls needs ⌊(x − 1) / m⌋ splits to end up entirely in pieces of size at most m. If those splits, summed over all bags, fit within the budget, cap m is achievable.

Inputnums = [2, 4, 8, 2], maxOperations = 4

Output2

Split 8 into 4+4, each new 4 into 2+2, and the original 4 into 2+2 — four operations leave every bag holding at most 2 balls.

nums (comma-separated)

maxOperations

def minimum_size(nums, max_operations):
    lo, hi = 1, max(nums)
    while lo < hi:                       # binary search the cap
        mid = (lo + hi) // 2
        ops = sum((x - 1) // mid for x in nums)
        if ops <= max_operations:        # cap works, try smaller
            hi = mid
        else:                            # over budget, raise cap
            lo = mid + 1
    return lo

function minimumSize(nums, maxOperations) {
  let lo = 1, hi = Math.max(...nums);
  while (lo < hi) {                     // binary search the cap
    const mid = (lo + hi) >> 1;
    let ops = 0;
    for (const x of nums) ops += Math.floor((x - 1) / mid);
    if (ops <= maxOperations) hi = mid; // cap works, try smaller
    else lo = mid + 1;                  // over budget, raise cap
  }
  return lo;
}

int minimumSize(int[] nums, int maxOperations) {
    int lo = 1, hi = 0;
    for (int x : nums) hi = Math.max(hi, x);
    while (lo < hi) {                     // binary search the cap
        int mid = (lo + hi) >>> 1;
        long ops = 0;
        for (int x : nums) ops += (x - 1) / mid;
        if (ops <= maxOperations) hi = mid; // cap works, try smaller
        else lo = mid + 1;                  // over budget, raise cap
    }
    return lo;
}

int minimumSize(vector<int>& nums, int maxOperations) {
    int lo = 1, hi = *max_element(nums.begin(), nums.end());
    while (lo < hi) {                     // binary search the cap
        int mid = lo + (hi - lo) / 2;
        long long ops = 0;
        for (int x : nums) ops += (x - 1) / mid;
        if (ops <= maxOperations) hi = mid; // cap works, try smaller
        else lo = mid + 1;                  // over budget, raise cap
    }
    return lo;
}

Explanation

We never decide which bag to split — we binary search the answer. The key observation is that feasibility is monotonic: if every bag can be brought down to size ≤ m within the budget, then any looser cap m + 1, m + 2, … is also achievable with the same (or fewer) splits. That yes/no boundary is exactly what binary search finds.

Checking one cap is cheap. A bag of x balls must end up as ⌈x / m⌉ pieces of size at most m, and each split adds exactly one bag, so it needs ⌈x / m⌉ − 1 = ⌊(x − 1) / m⌋ operations. Summing this over all bags and comparing against maxOperations tells us whether cap m is achievable in O(n).

The search runs on values, not indices: lo = 1 (a bag can never be smaller) and hi = max(nums) (doing nothing already achieves this). When mid is feasible we keep it as a candidate and shrink with hi = mid; when it is not, even the best play cannot reach it, so lo = mid + 1. The loop converges on the smallest feasible cap.

Walking the default example nums = [2, 4, 8, 2], maxOperations = 4: cap 4 needs 0+0+1+0 = 1 split — feasible, so hi = 4. Cap 2 needs 0+1+3+0 = 4 splits — exactly the budget, feasible, so hi = 2. Cap 1 needs 1+3+7+1 = 12 splits — far over budget, so lo = 2. Now lo = hi = 2: the minimum penalty is 2.

Each feasibility check scans the n bags once, and the value range [1, max(nums)] halves every iteration, so the total work is O(n log max(nums)) with O(1) extra space. Greedy or heap-based splitting cannot match this, because the best split for one cap is wrong for another — the binary search sidesteps that choice entirely.

Time: O(n log max(nums)) Space: O(1)