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:
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.
Example 2:
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.
Constraints:
1 <= nums.length <= 1051 <= maxOperations, nums[i] <= 109This approach leverages binary search to efficiently minimize the penalty. The idea is to use binary search to determine the minimum possible 'penalty', where penalty is defined as the maximum number of balls allowed in any bag.
We set our binary search range from 1 to the maximum number of balls in any bag initially. For each mid value (potential penalty), we check if it's possible to achieve this penalty with the given number of operations. We do this by calculating how many operations we'd need to make every bag have at most 'mid' number of balls. If we can do that within the allowed number of operations, we adjust our search range to potentially lower penalties; otherwise, we increase our search range.
The C solution uses a helper function canAchievePenalty which computes whether it's possible to split the balls such that the maximum number of balls in any bag does not exceed the proposed penalty, within the given number of operations. The main function minimumPenalty then uses binary search over this helper to find the minimum possible penalty.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log(max(nums)))
Space Complexity: O(1)
Another approach is to continuously divide the largest bags using a priority queue to keep track of the largest bag sizes. By always splitting the largest bag first, we aim to reduce the penalty faster. This works similarly to the binary search approach in terms of dividing the problem space but uses a different method to handle priorities.
The greedy approach employs priority queue logic indirectly by sorting the array in descending order initially. It repeatedly considers the largest current value, using a strategy similar to the binary search solution.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n + n log(max(nums)))
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Binary Search on Penalty | Time Complexity: O(n log(max(nums))) |
| Greedy Approach with Priority Queue | Time Complexity: O(n log n + n log(max(nums))) |
Minimum Limit of Balls in a Bag - Leetcode 1760 - Python • NeetCodeIO • 16,148 views views
Watch 9 more video solutions →Practice Minimum Limit of Balls in a Bag with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor