51. Minimum Limit of Balls in a Bag

Topic :

binary search

Difficulty :

medium

Problem Link :

problem statement

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

solution

TIME COMPLEXITY : O(NlogN)

SPACE COMPLEXITY : O(1)

import java.io.*;
import java.util.*;
 class Minimum_Limit_of_Balls_in_a_Bag
{
  public static void main(String args[])
  {
     int[]nums = {2,4,8,2};
     int maxOperations = 4;
     System.out.println(minimumSize(nums,maxOperations));
  }
  static int minimumSize(int[] nums, int maxOperations)
  { 
      Arrays.sort(nums);
      int res=0;  
      int low=1;
      int high=nums[nums.length-1];
      // we will check if what could be the max number as penalty using binary search  
      while(low<=high)
      {
          int mid=(low+high)/2;
          // check  if it is possible to achieve this maxNumber in maxOperations
          if(isPossible(nums,mid,maxOperations)) //if it is possible
          {
             res=mid;// this might be our probable ans
             high=mid-1; // try to minimize it 
          }
          else // try for a greater maxNumber
          {
              low=mid+1;
          }
      }
      return res;
  }    
  static boolean isPossible(int nums[], int maxNumber, int maxOperations)
  {
        int currOperations=0;
        for(int i=0;i<nums.length;i++)
        {
            if(nums[i]>maxNumber)
            {
                //important check
                if(nums[i]%maxNumber==0)
                currOperations+=nums[i]/maxNumber -1;
                else
                currOperations+=nums[i]/maxNumber;     
            }
            
            if(currOperations>maxOperations) return false;
        }
        return true;
   }
}