Minimum Limit of Balls in a Bag
Medium · Binary Search · Array · Binary Search
Problem
You are given an integer array nums, where bag i holds nums[i] balls, and an integer maxOperations. In one operation you pick any bag and split it into two new bags, each holding a positive number of balls, with the same total.
Your penalty is the largest number of balls in any single bag. Using at most maxOperations operations, return the minimum possible penalty.
Examples
Input: nums = [12,5], maxOperations = 3 Output: 4
Split 12 into 4 + 4 + 4 (two operations) and 5 into 4 + 1 (one operation), leaving no bag above 4.
Input: nums = [6,6,6], maxOperations = 2 Output: 6
Only two of the three bags can be split, so one bag of 6 remains.
Input: nums = [9], maxOperations = 2 Output: 3
Two splits turn 9 into three bags of 3.
Constraints
- 1 <= len(nums) <= 10^5
- 1 <= maxOperations, nums[i] <= 10^9
Approaches
- Baseline: try each penalty from a lower bound up — time O(n · M), space O(1)
Follow-up
What if one operation could split a bag into two or three? Only the cost of a penalty changes: a bag needing k pieces now costs ceil((k - 1) / 2) operations, and the binary search stays (see the use case “Splits into up to three bags”).
Related problems
Start free on Cariara · Coding problems · System design studio
