Code Implementation

class Solution:
    def minimumSize(self, nums, maxOperations):
        def can_split(limit):
            ops = 0
            for balls in nums:
                # Each bag needs (balls-1)//limit splits (integer division)
                ops += (balls - 1) // limit
            return ops <= maxOperations
        
        left, right = 1, max(nums)
        answer = right
        while left <= right:
            mid = (left + right) // 2
            if can_split(mid):
                answer = mid
                right = mid - 1
            else:
                left = mid + 1
        return answer
      

class Solution {
public:
    bool canSplit(vector<int>& nums, int maxOperations, int limit) {
        int ops = 0;
        for (int balls : nums) {
            ops += (balls - 1) / limit;
        }
        return ops <= maxOperations;
    }
    int minimumSize(vector<int>& nums, int maxOperations) {
        int left = 1, right = *max_element(nums.begin(), nums.end());
        int answer = right;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canSplit(nums, maxOperations, mid)) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }
};
      

class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        int left = 1, right = 0;
        for (int num : nums) right = Math.max(right, num);
        int answer = right;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canSplit(nums, maxOperations, mid)) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }
    
    private boolean canSplit(int[] nums, int maxOperations, int limit) {
        int ops = 0;
        for (int balls : nums) {
            ops += (balls - 1) / limit;
        }
        return ops <= maxOperations;
    }
}
      

var minimumSize = function(nums, maxOperations) {
    const canSplit = (limit) => {
        let ops = 0;
        for (let balls of nums) {
            ops += Math.floor((balls - 1) / limit);
        }
        return ops <= maxOperations;
    };
    let left = 1, right = Math.max(...nums);
    let answer = right;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (canSplit(mid)) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return answer;
};
      

Problem Description

You are given an array nums where each element represents the number of balls in a bag. You can perform up to maxOperations operations. In each operation, you may take any bag and split it into two bags with a positive number of balls in each (the sum remains the same). The goal is to minimize the largest number of balls in any single bag after performing at most maxOperations splits.

• Each operation splits one bag into two bags.
• You can split a bag more than once, as long as the total operations do not exceed maxOperations.
• You must return the minimum possible value of the largest bag size after all operations.
• There is always at least one solution.

Thought Process

At first glance, the problem seems to ask for distributing balls as evenly as possible. The brute-force way would be to try all possible ways to split the bags, but this quickly becomes infeasible with large arrays or big numbers.

The key insight is to recognize that the problem is about minimizing the maximum bag size using a limited number of splits. Instead of tracking every possible distribution, we can reframe the problem: for a given maximum allowed bag size, can we achieve it with at most maxOperations splits? If so, maybe we can do even better; if not, we need to allow larger bags.

This is a classic scenario for binary search on the answer. We search for the smallest possible maximum bag size that can be achieved with the allowed number of operations.

Solution Approach

We use binary search to efficiently find the minimum possible limit for the largest bag size:

1. Define the search space:
   • The smallest possible bag size is 1 (can't have zero balls).
   • The largest possible bag size is the largest number in nums (no splits at all).
2. Binary search loop:
   • For each candidate maximum size (midpoint of search space), check if it's possible to split the bags such that no bag exceeds this size, using at most maxOperations splits.
   • If possible, try a smaller maximum (move right pointer down).
   • If not possible, try a larger maximum (move left pointer up).
3. How to check feasibility:
   • For each bag, compute how many splits are needed to make all resulting bags have at most the candidate size.
   • For a bag with balls balls and candidate size limit, the number of splits needed is (balls - 1) // limit. This formula works because splitting a bag into ceil(balls / limit) bags requires ceil(balls / limit) - 1 splits, and (balls - 1) // limit gives the same result.
   • Sum the splits for all bags; if the total is at most maxOperations, it's feasible.
4. Return the smallest feasible candidate.

Example Walkthrough

Suppose nums = [9, 7, 3] and maxOperations = 2.

1. Initial search space: left = 1, right = 9 (max of nums).
2. First mid = 5:
   • Bag 9: (9-1)//5 = 1 split
   • Bag 7: (7-1)//5 = 1 split
   • Bag 3: (3-1)//5 = 0 splits
   • Total splits = 2 (fits maxOperations)
   • Feasible! Try smaller: right = 4
3. Next mid = 2:
   • Bag 9: (9-1)//2 = 4 splits
   • Bag 7: (7-1)//2 = 3 splits
   • Bag 3: (3-1)//2 = 1 split
   • Total splits = 8 (too many)
   • Not feasible. Try larger: left = 3
4. Next mid = 3:
   • Bag 9: (9-1)//3 = 2 splits
   • Bag 7: (7-1)//3 = 2 splits
   • Bag 3: (3-1)//3 = 0 splits
   • Total splits = 4 (too many)
   • Not feasible. Try larger: left = 4
5. Next mid = 4:
   • Bag 9: (9-1)//4 = 2 splits
   • Bag 7: (7-1)//4 = 1 split
   • Bag 3: (3-1)//4 = 0 splits
   • Total splits = 3 (too many)
   • Not feasible. Try larger: left = 5
6. Left passes right (left = 5, right = 4), so answer is 5.

After at most 2 splits, the smallest possible largest bag is 5.

Time and Space Complexity

• Brute-force: Try all possible ways to split bags, which is exponential and infeasible for large inputs.
• Optimized (Binary Search) Approach:
  • Binary search runs in O(log(max(nums))) iterations.
  • Each iteration checks all bags: O(n) per check.
  • Total time: O(n * log(max(nums))).
  • Space: O(1) extra space (not counting input).

Summary

By reframing the problem as a search for the minimal possible maximum bag size, we avoid brute-force enumeration and instead use binary search. The key insight is that for any candidate bag size, we can efficiently check if it is achievable with the allowed number of splits. This makes the solution both elegant and efficient, scaling well even for large input sizes.