Show problems as
Classic problem #1760MediumArrayBinary Search

Minimum Limit of Balls in a Bag

Real-world version: Smallest Tallest Stack After Splits
Tracked in this browser only
Read Minimum Limit of Balls in a Bag on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A depot floor holds several stacks of cartons. stacks[i] is the number of cartons in stack i.

One split takes a single stack off the floor and puts back two stacks in its place, each holding at least one carton, together holding exactly what the original stack held. A stack put back may be split again later. You are allowed at most splits splits, and you may also use fewer, or none at all.

The peak of the floor is the number of cartons in its tallest stack. Return the smallest peak you can leave behind.

Examples

Example 1

Input
stacks = [9, 9], splits = 2
Output
5

Split each stack of 9 into 5 and 4, using both allowed splits. The floor then holds 5, 4, 5 and 4 cartons, so its peak is 5.

Example 2

Input
stacks = [4, 4], splits = 1
Output
4

One split is allowed. Splitting a stack of 4 into 2 and 2 leaves the floor holding 2, 2 and 4 cartons, whose peak is 4. Carrying out no split at all also leaves a peak of 4.

Example 3

Input
stacks = [1, 1, 1], splits = 2
Output
1

Every stack already holds a single carton and a split has to leave at least one carton on each side, so no split is possible and the peak is 1.

Constraints

  • 1 <= stacks.length <= 10^5
  • 1 <= splits <= 10^9
  • 1 <= stacks[i] <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def minimum_size(stacks: list[int], splits: int) -> int:
Java
public int minimumSize(int[] stacks, int splits)

More on the same topics