Minimum Limit of Balls in a Bag

Q: Can you also say how to split the bags for the optimal answer?

Once you know the limit m, split each bag of x balls into ceil(x / m) parts as evenly as possible. That uses exactly (x - 1) // m splits per bag and never exceeds m.

Q: Where else does this pattern apply?

Any "minimize the largest" or "maximize the smallest" problem with a monotonic check: Koko eating bananas, splitting an array into k parts with the smallest largest sum, shipping packages within d days, and placing routers as far apart as possible.

Q: What if each split could produce up to three bags?

Only the check changes. A bag of x balls needs ceil(x / m) final bags, and each operation adds at most two, so it needs ceil((ceil(x / m) - 1) / 2) operations. The binary search is unchanged.

Split bags of balls with a limited number of operations to make the largest bag as small as possible. A classic "binary search on the answer" problem. Solve it below in Python or JavaScript, then read the walkthrough.

Solve it in your browser Read the solution

MediumArray Binary Search Asked at 95 companies incl. Google, Amazon, Meta

Problem

You have some bags of balls: bag i holds nums[i] balls. You may perform at most maxOperations operations. In one operation you take any bag and split it into two new bags, each holding a positive number of balls, whose sizes add up to the original.

Your penalty is the number of balls in the largest bag once you're done. Return the smallest penalty you can achieve.

Example 1

Input: nums = [9], maxOperations = 2
Output: 3

Split 9 into 6 and 3, then 6 into 3 and 3. All bags hold 3.

Example 2

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

Splitting 4 takes one operation and splitting 8 into four 2s takes three.

Example 3

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

Two splits turn 17 into 7, 7 and 3. Getting every bag down to 6 would need 1 + 2 = 3 operations.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ maxOperations, nums[i] ≤ 10⁹
Every bag must always hold at least one ball, so the answer is at least 1.

Practice

Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Minimum Limit of Balls in a Bag in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Minimum Limit of Balls in a Bag

Pattern: Binary search on the answer

Deciding how to split is hard. Checking a proposed answer is easy. If you want every bag to hold at most m balls, a bag of size x needs to become ceil(x / m) bags, which takes ceil(x / m) - 1 = (x - 1) // m splits. Add those up and compare with maxOperations.

That check is monotonic: if a limit m is reachable, any larger limit is too. So binary search over m from 1 to max(nums) for the smallest limit that passes.

Approach 1: Greedily halve the largest bag

Repeatedly split the biggest bag in half using a max-heap. It feels right but is wrong: a bag of 9 with 2 operations should become 3, 3, 3, while halving gives 5 and 4, then 4, 3, 2 with a penalty of 4. It is also slow when maxOperations is huge.

Time O(ops · log n), and incorrect · Space O(n)

Approach 2: Try every limit from 1 upward

Test m = 1, 2, 3, ... with the split-count check and stop at the first that fits. Correct, but the answer can be close to 10⁹.

Time O(n · max(nums)) · Space O(1)

Approach 3: Binary search the limit

lo = 1, hi = max(nums) (that limit needs zero splits).
While lo < hi: let mid = (lo + hi) // 2. Count sum((x - 1) // mid). If it is at most maxOperations, set hi = mid; otherwise lo = mid + 1.
Return lo.

Each check is O(n), and there are about 30 of them.

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

Approach	Time	Space
Greedily halve the largest bag	O(ops · log n), and incorrect	O(n)
Try every limit from 1 upward	O(n · max(nums))	O(1)
Binary search the limit	O(n log max(nums))	O(1)

Solution code

Try the practice editor first. Both solutions pass every test above.

Minimum Limit of Balls in a Bag solution in Python

def minimum_size(nums: list[int], max_operations: int) -> int:
    lo, hi = 1, max(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        splits = sum((x - 1) // mid for x in nums)
        if splits <= max_operations:
            hi = mid
        else:
            lo = mid + 1
    return lo

Minimum Limit of Balls in a Bag solution in JavaScript

function minimumSize(nums, maxOperations) {
  let lo = 1;
  let hi = nums.reduce((a, b) => Math.max(a, b), 1);
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    let splits = 0;
    for (const x of nums) splits += Math.floor((x - 1) / mid);
    if (splits <= maxOperations) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Common mistakes

Halving the largest bag greedily, which is not optimal when a bag should be split into three or more equal parts.
Counting splits as `x // m` instead of `(x - 1) // m`. A bag of exactly m balls needs no split.
Starting the search at 0, which causes division by zero.
Overflowing a 32-bit counter when summing splits. With 10⁵ bags of 10⁹ balls the total can exceed 2³¹. You can also stop counting as soon as it passes maxOperations.

What interviewers look for

Signal the pattern early: "minimize the maximum" plus a cheap yes/no check means binary search on the answer. Interviewers want to hear you state the feasibility function and argue it is monotonic before you write any code.

Walk through the split formula on one bag, such as 9 balls with a limit of 4 needing 2 splits, and mention why the greedy halving idea fails.

Follow-up questions

Can you also say how to split the bags for the optimal answer?

Once you know the limit m, split each bag of x balls into ceil(x / m) parts as evenly as possible. That uses exactly (x - 1) // m splits per bag and never exceeds m.

Where else does this pattern apply?

Any "minimize the largest" or "maximize the smallest" problem with a monotonic check: Koko eating bananas, splitting an array into k parts with the smallest largest sum, shipping packages within d days, and placing routers as far apart as possible.

What if each split could produce up to three bags?

Only the check changes. A bag of x balls needs ceil(x / m) final bags, and each operation adds at most two, so it needs ceil((ceil(x / m) - 1) / 2) operations. The binary search is unchanged.

Companies that ask Minimum Limit of Balls in a Bag

Minimum Limit of Balls in a Bag is tagged by 95 companies in our interview dataset. The score shows how often it comes up at each company.

and 71 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Minimum Limit of Balls in a Bag

Solve it in your browser Read the solution

MediumArray Binary Search Asked at 95 companies incl. Google, Amazon, Meta

Problem

Your penalty is the number of balls in the largest bag once you're done. Return the smallest penalty you can achieve.

Example 1

Input: nums = [9], maxOperations = 2
Output: 3

Split 9 into 6 and 3, then 6 into 3 and 3. All bags hold 3.

Example 2

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

Splitting 4 takes one operation and splitting 8 into four 2s takes three.

Example 3

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

Two splits turn 17 into 7, 7 and 3. Getting every bag down to 6 would need 1 + 2 = 3 operations.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ maxOperations, nums[i] ≤ 10⁹
Every bag must always hold at least one ball, so the answer is at least 1.

Practice

Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Minimum Limit of Balls in a Bag in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Minimum Limit of Balls in a Bag

Pattern: Binary search on the answer

That check is monotonic: if a limit m is reachable, any larger limit is too. So binary search over m from 1 to max(nums) for the smallest limit that passes.

Approach 1: Greedily halve the largest bag

Time O(ops · log n), and incorrect · Space O(n)

Approach 2: Try every limit from 1 upward

Test m = 1, 2, 3, ... with the split-count check and stop at the first that fits. Correct, but the answer can be close to 10⁹.

Time O(n · max(nums)) · Space O(1)

Approach 3: Binary search the limit

lo = 1, hi = max(nums) (that limit needs zero splits).
While lo < hi: let mid = (lo + hi) // 2. Count sum((x - 1) // mid). If it is at most maxOperations, set hi = mid; otherwise lo = mid + 1.
Return lo.

Each check is O(n), and there are about 30 of them.

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

Approach	Time	Space
Greedily halve the largest bag	O(ops · log n), and incorrect	O(n)
Try every limit from 1 upward	O(n · max(nums))	O(1)
Binary search the limit	O(n log max(nums))	O(1)

Solution code

Try the practice editor first. Both solutions pass every test above.

Minimum Limit of Balls in a Bag solution in Python

def minimum_size(nums: list[int], max_operations: int) -> int:
    lo, hi = 1, max(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        splits = sum((x - 1) // mid for x in nums)
        if splits <= max_operations:
            hi = mid
        else:
            lo = mid + 1
    return lo

Minimum Limit of Balls in a Bag solution in JavaScript

function minimumSize(nums, maxOperations) {
  let lo = 1;
  let hi = nums.reduce((a, b) => Math.max(a, b), 1);
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    let splits = 0;
    for (const x of nums) splits += Math.floor((x - 1) / mid);
    if (splits <= maxOperations) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Common mistakes

Halving the largest bag greedily, which is not optimal when a bag should be split into three or more equal parts.
Counting splits as `x // m` instead of `(x - 1) // m`. A bag of exactly m balls needs no split.
Starting the search at 0, which causes division by zero.
Overflowing a 32-bit counter when summing splits. With 10⁵ bags of 10⁹ balls the total can exceed 2³¹. You can also stop counting as soon as it passes maxOperations.

What interviewers look for

Walk through the split formula on one bag, such as 9 balls with a limit of 4 needing 2 splits, and mention why the greedy halving idea fails.

Follow-up questions

Can you also say how to split the bags for the optimal answer?

Once you know the limit m, split each bag of x balls into ceil(x / m) parts as evenly as possible. That uses exactly (x - 1) // m splits per bag and never exceeds m.

Where else does this pattern apply?

What if each split could produce up to three bags?

Only the check changes. A bag of x balls needs ceil(x / m) final bags, and each operation adds at most two, so it needs ceil((ceil(x / m) - 1) / 2) operations. The binary search is unchanged.

Companies that ask Minimum Limit of Balls in a Bag

Minimum Limit of Balls in a Bag is tagged by 95 companies in our interview dataset. The score shows how often it comes up at each company.

and 71 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Problem

Constraints

Practice

How to solve Minimum Limit of Balls in a Bag

Approach 1: Greedily halve the largest bag

Approach 2: Try every limit from 1 upward

Approach 3: Binary search the limit

Solution code

Common mistakes

What interviewers look for

Follow-up questions

Can you also say how to split the bags for the optimal answer?

Where else does this pattern apply?

What if each split could produce up to three bags?

Companies that ask Minimum Limit of Balls in a Bag

Practice next

Get live help in the real interview

Problem

Constraints

Practice

How to solve Minimum Limit of Balls in a Bag

Approach 1: Greedily halve the largest bag

Approach 2: Try every limit from 1 upward

Approach 3: Binary search the limit

Solution code

Common mistakes

What interviewers look for

Follow-up questions

Can you also say how to split the bags for the optimal answer?

Where else does this pattern apply?

What if each split could produce up to three bags?

Companies that ask Minimum Limit of Balls in a Bag

Practice next

Get live help in the real interview