1760. 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.

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 <= 105
• 1 <= maxOperations, nums[i] <= 109

Approach 01:

class Solution {
 public:
  int minimumSize(vector<int>& nums, int maxOperations) {
    int low = 1;
    int high = ranges::max(nums);

    while (low < high) {
      const int mid = (low + high) / 2;
      if (numOperations(nums, mid) <= maxOperations)
        high = mid;
      else
        low = mid + 1;
    }

    return low;
  }

 private:
  // Returns the number of operations required to make mid the penalty.
  int numOperations(const vector<int>& nums, int mid) {
    int totalOperations = 0;
    for (const int currentNum : nums)
      totalOperations += (currentNum - 1) / mid;
    return totalOperations;
  }
};

class Solution:
    def minimumSize(self, nums: list[int], maxOperations: int) -> int:
        low = 1
        high = max(nums)

        while low < high:
            mid = (low + high) // 2
            if self.numOperations(nums, mid) <= maxOperations:
                high = mid
            else:
                low = mid + 1

        return low

    # Returns the number of operations required to make mid the penalty.
    def numOperations(self, nums: list[int], mid: int) -> int:
        totalOperations = 0
        for currentNum in nums:
            totalOperations += (currentNum - 1) // mid
        return totalOperations

Time Complexity

• Binary Search:
  • The binary search operates on the range \([1, \text{max(nums)}]\), where \(\text{max(nums)} = k\).
  • Binary search takes \(O(\log k)\), where \(k\) is the largest number in the array nums.
• Number of Operations Calculation:
  • For each midpoint during binary search, the function numOperations iterates over all elements in nums to calculate the required number of operations.
  • This contributes \(O(n)\) per midpoint, where \(n\) is the size of the array nums.
• Overall Time Complexity:

  The binary search runs \(O(\log k)\) times, and each iteration involves an \(O(n)\) operation. Therefore, the total time complexity is \(O(n \cdot \log k)\), where \(n\) is the size of the array and \(k\) is the largest number in the array.

Space Complexity

• Auxiliary Variables:

  The function uses integer variables like low, high, mid, and totalOperations, requiring \(O(1)\) space.

• No Additional Data Structures:

  The function does not use any extra data structures aside from the input array, which does not count towards space complexity.

• Overall Space Complexity:

  The space complexity is \(O(1)\).