1760. Minimum Limit of Balls in a Bag LeetCode Solution
In this guide, you will get 1760. Minimum Limit of Balls in a Bag LeetCode Solution with the best time and space complexity. The solution to Minimum Limit of Balls in a Bag problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Limit of Balls in a Bag
You are given an integer array nums where the ith bag contains nums[i] balls. You are also given an integer maxOperations.
You can perform the following operation at most maxOperations times:
Take any bag of balls and divide it into two new bags with a positive number of balls.
For example, a bag of 5 balls can become two new bags of 1 and 4 balls, or two new bags of 2 and 3 balls.
Your penalty is the maximum number of balls in a bag. You want to minimize your penalty after the operations.
Return the minimum possible penalty after performing the operations.
Example 1:
Input: nums = [9], maxOperations = 2
Output: 3
Explanation:
– Divide the bag with 9 balls into two bags of sizes 6 and 3. [9] -> [6,3].
– Divide the bag with 6 balls into two bags of sizes 3 and 3. [6,3] -> [3,3,3].
The bag with the most number of balls has 3 balls, so your penalty is 3 and you should return 3.
Input: nums = [2,4,8,2], maxOperations = 4
Output: 2
Explanation:
– Divide the bag with 8 balls into two bags of sizes 4 and 4. [2,4,8,2] -> [2,4,4,4,2].
– Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,4,4,4,2] -> [2,2,2,4,4,2].
– Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
– Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].
The bag with the most number of balls has 2 balls, so your penalty is 2, and you should return 2.
1760. Minimum Limit of Balls in a Bag LeetCode Solution in C++
class Solution {
public:
int minimumSize(vector<int>& nums, int maxOperations) {
int l = 1;
int r = ranges::max(nums);
while (l < r) {
const int m = (l + r) / 2;
if (numOperations(nums, m) <= maxOperations)
r = m;
else
l = m + 1;
}
return l;
}
private:
// Returns the number of operations required to make m penalty.
int numOperations(const vector<int>& nums, int m) {
int operations = 0;
for (const int num : nums)
operations += (num - 1) / m;
return operations;
}
}; /* code provided by PROGIEZ */
1760. Minimum Limit of Balls in a Bag LeetCode Solution in Java
class Solution {
public int minimumSize(int[] nums, int maxOperations) {
int l = 1;
int r = Arrays.stream(nums).max().getAsInt();
while (l < r) {
final int m = (l + r) / 2;
if (numOperations(nums, m) <= maxOperations)
r = m;
else
l = m + 1;
}
return l;
}
// Returns the number of operations required to make m penalty.
private int numOperations(int[] nums, int m) {
int operations = 0;
for (final int num : nums)
operations += (num - 1) / m;
return operations;
}
} // code provided by PROGIEZ
1760. Minimum Limit of Balls in a Bag LeetCode Solution in Python
class Solution:
def minimumSize(self, nums: list[int], maxOperations: int) -> int:
def numOperations(m: int) -> int:
"""Returns the number of operations required to make m penalty."""
return sum((num - 1) // m for num in nums)
l = 1
r = max(nums)
return bisect.bisect_left(
range(l, r),
True, key=lambda m: numOperations(m) <= maxOperations) + l # code by PROGIEZ
