Problem

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.

Examples

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 <= 10^5
  • 1 <= maxOperations, nums[i] <= 10^9

Solution

Method 1 - Binary Search

The minimum possible penalty can start from 1, while the maximum possible penalty corresponds to the maximum element in the array. This defines the range within which our answer lies. By using a helper function that determines whether a specific penalty is achievable given the allowed number of operations, we can employ binary search within this range to identify the minimum possible penalty.

Helper Function: The helper function calculates the total number of operations needed to ensure every bag has balls less than or equal to the current assumed penalty. If the required operations are less than or equal to the given maxOperations, then achieving this penalty is possible.

Binary Search Approach

  1. Define the Search Range: The range for binary search is from 1 (the smallest possible penalty) to the maximum element in the array nums (the largest possible penalty).
  2. Binary Search Execution:
    • Calculate the midpoint (mid) of the current range.
    • Use the helper function to check if it’s possible to achieve this midpoint penalty with the given number of operations.
    • If it’s possible, update the minimum penalty (minPenalty) and adjust the search range to look for even smaller penalties.
    • If it’s not possible, adjust the search range to look for larger penalties.

Code

Java
class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        int left = 1;
        int right = Arrays.stream(nums).max().getAsInt();
        int minPenalty = right;

        // binary search on possible range
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canDivide(nums, maxOperations, mid)) {
                minPenalty = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return minPenalty;
    }
    
    private boolean canDivide(int[] nums, int maxOperations, int maxSize) {
        int operations = 0;
        for (int num : nums) {
            operations += (num - 1) / maxSize;
        }
        return operations <= maxOperations;
    }
}
Python
class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        def can_divide(max_size: int) -> bool:
            operations = sum((num - 1) // max_size for num in nums)
            return operations <= maxOperations

        left, right = 1, max(nums)
        minPenalty = right

        # binary search on possible range
        while left <= right:
            mid = left + (right - left) // 2
            if can_divide(mid):
                minPenalty = mid
                right = mid - 1
            else:
                left = mid + 1

        return minPenalty

Complexity

  • ⏰ Time complexity: O(n log(max(nums))), where n is the length of the array nums. This comes from performing binary search over the range [1, max(nums)] and checking the feasibility within O(n) time.
  • 🧺 Space complexity: O(1), since we are using a constant amount of extra space.