Minimum Limit of Balls in a Bag

Leetcode Problem:

• Minimum Limit of Balls in a Bag

Summary

• Find the minimum possible penalty after performing operations on bags of balls.

Approach

• Binary search approach to find the minimum possible penalty
• The idea is to perform binary search on the possible maximum number of balls in a bag
• The binary search is performed on the range [1, max balls in a bag]
• For each mid value, it checks if the number of operations required to divide all bags into smaller bags is less than or equal to maxOperations
• If it is, then the minimum possible penalty is updated and the search space is narrowed down to the lower half of the range
• If not, the search space is narrowed down to the upper half of the range.

Complexity

• O(n log m) where n is the number of bags and m is the maximum number of balls in a bag.

Explanation

• The solution uses a binary search approach to find the minimum possible penalty
• The binary search is performed on the possible maximum number of balls in a bag, which is represented by the variable mid
• For each mid value, it checks if the number of operations required to divide all bags into smaller bags is less than or equal to maxOperations
• If it is, then the minimum possible penalty is updated and the search space is narrowed down to the lower half of the range
• If not, the search space is narrowed down to the upper half of the range
• This process is repeated until the minimum possible penalty is found.

Solution Code:

class Solution {
public:
    
    
    int minimumSize(vector& nums, int maxOperations) {
        int _max = 0;
        for(int i = 0 ; i < nums.size(); i++){
            if (_max < nums[i]){
                _max = nums[i];
            }
        }
        int l = 1; 
        int r = _max;
        int ans = _max;
        while(l <= r){
            int mid = l + (r - l)/2;
            cout << mid << endl;
            int operation = maxOperations;
            bool success = true;
            for(int i = 0 ; i < nums.size(); i++){
                if(mid < nums[i]){
                    operation -= ((nums[i] + mid - 1) / mid) - 1;
                }
                if(operation < 0){
                    success = false;
                    break;
                }
            }
            if(success){
                r = mid -1;
                ans = mid;
            } else{
                l= mid + 1;
            }

        }        

        return ans;
    }
};