Minimize the Maximum Number of Balls in a Bucket
Given an array arr[] and a positive integer K, where arr[i] represent number of balls in the ith bucket. The task is to minimize the maximum number of balls in a bucket by performing operation at most K times. The operation is to take any bucket and divide it into two new buckets with a positive number of balls in it. For example, a bucket of 5 balls can be divided into two new buckets of 1 and 4 balls, or two new buckets of 3 and 2 balls.
Examples:
Input: arr = {9}, K = 2
Output: 3
Explanation: Divide the bucket with 9 balls into two buckets of sizes 6 and 3. {9} -> {6,3}. Divide the bucket with 6 balls into two buckets of sizes 3 and 3. {6,3} -> {3,3,3}. The bucket with the most number of balls has 3 balls, so your penalty is 3 and you should return 3.Input: arr = {2,4,8,2}, K = 4
Output: 2
Approach:
The binary search efficiently identifies the minimum size for buckets by iteratively narrowing the search space between the minimum and maximum initial bucket sizes. The isPossible function checks if achieving a specified maximum bucket size is feasible within a given limit of operations. This approach optimally explores the solution space, resulting in the minimum possible maximum number of balls in a bucket that satisfies the conditions.
Steps to solve the problem:
- isPossible Function:
- For each number n in the array:
- Calculate how many times mid can fit into n.
- If n is divisible by mid, subtract 1 from the count.
- Sum up these counts to get the total required operations.
- Check if the total operations are less than or equal to the given limit K.
- Return true if it is possible, otherwise return false.
- For each number n in the array:
- minimumSize Function:
- Set the initial search range (start and end).
- Initialize result to the maximum element in the array.
- Use binary search to find the minimum size:
- Calculate the middle value mid.
- If it is possible to achieve this mid using isPossible:
- Update result and adjust the search range.
- If not possible, adjust the search range accordingly
Below is the implementation of the above approach:
C++
#include <algorithm> #include <iostream> #include <vector> using namespace std; bool isPossible(vector< int >& arr, int K, int mid) { int requiredOps = 0; for ( int n : arr) { // no. of operations required to bring n less than // or eq to curr assumed mid int x = n / mid; // if n is divisible by mid, need to subtract 1 if (n % mid == 0) x--; requiredOps += x; } // getting current mid is possible only if required // ops is <= maxOps return requiredOps <= K; } int minimumSize(vector< int >& arr, int K) { int start = 1, end = *max_element(arr.begin(), arr.end()); int result = end; // binary search on possible range while (start <= end) { int mid = start + (end - start) / 2; if (isPossible(arr, K, mid)) result = mid, end = mid - 1; else start = mid + 1; } return result; } int main() { vector< int > arr = { 2, 4, 8, 2 }; int K = 4; // Call the function and print the result int result = minimumSize(arr, K); cout << result << endl; return 0; } |
Java
import java.util.*; public class GFG { // Function to check if it's possible to achieve the condition static boolean isPossible(List<Integer> arr, int K, int mid) { int requiredOps = 0 ; for ( int n : arr) { int x = n / mid; if (n % mid == 0 ) x--; // If n is divisible by mid, reduce x by 1 requiredOps += x; // Accumulate required operations } // Check if requiredOps is within the limit return requiredOps <= K; } // Function to find the minimum size that satisfies the condition static int minimumSize(List<Integer> arr, int K) { int start = 1 ; int end = Collections.max(arr); // Set the end of the search range as the maximum element in arr int result = end; // Initialize the result as the maximum element initially while (start <= end) { int mid = start + (end - start) / 2 ; // Calculate the midpoint if (isPossible(arr, K, mid)) { result = mid; // Update result if the current mid is possible end = mid - 1 ; // Search in the left half of the range } else { start = mid + 1 ; // Search in the right half of the range } } return result; // Return the final result } public static void main(String[] args) { List<Integer> arr = new ArrayList<>(); arr.add( 2 ); arr.add( 4 ); arr.add( 8 ); arr.add( 2 ); int K = 4 ; // Call the function and print the result int result = minimumSize(arr, K); System.out.println(result); } } |
Python3
def is_possible(arr, K, mid): required_ops = 0 for n in arr: x = n / / mid if n % mid = = 0 : x - = 1 required_ops + = x return required_ops < = K def minimum_size(arr, K): start = 1 end = max (arr) result = end while start < = end: mid = start + (end - start) / / 2 if is_possible(arr, K, mid): result = mid end = mid - 1 else : start = mid + 1 return result if __name__ = = "__main__" : arr = [ 2 , 4 , 8 , 2 ] K = 4 # Call the function and print the result result = minimum_size(arr, K) print (result) # This code is contributed by akshitaguprzj3 |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // Function to check if it's possible to achieve the condition static bool IsPossible(List< int > arr, int K, int mid) { int requiredOps = 0; foreach ( int n in arr) { int x = n / mid; if (n % mid == 0) x--; // If n is divisible by mid, reduce x by 1 requiredOps += x; // Accumulate required operations } // Check if requiredOps is within the limit return requiredOps <= K; } // Function to find the minimum size that satisfies the condition static int MinimumSize(List< int > arr, int K) { int start = 1; int end = arr.Max(); // Set the end of the search range as the maximum element in arr int result = end; // Initialize the result as the maximum element initially while (start <= end) { int mid = start + (end - start) / 2; // Calculate the midpoint if (IsPossible(arr, K, mid)) { result = mid; // Update result if the current mid is possible end = mid - 1; // Search in the left half of the range } else { start = mid + 1; // Search in the right half of the range } } return result; // Return the final result } static void Main( string [] args) { List< int > arr = new List< int > { 2, 4, 8, 2 }; int K = 4; // Call the function and print the result int result = MinimumSize(arr, K); Console.WriteLine(result); } } |
Javascript
// Function to check if it's possible to achieve the condition const isPossible = (arr, K, mid) => { return arr.reduce((requiredOps, n) => { const x = Math.floor(n / mid) - (n % mid === 0 ? 1 : 0); return requiredOps + x; }, 0) <= K; }; // Function to find the minimum size that satisfies the condition const minimumSize = (arr, K) => { let start = 1; let end = Math.max(...arr); // Set the end of the search range as the maximum element in arr let result = end; // Initialize the result as the maximum element initially while (start <= end) { const mid = start + Math.floor((end - start) / 2); // Calculate the midpoint if (isPossible(arr, K, mid)) { result = mid; // Update result if the current mid is possible end = mid - 1; // Search in the left half of the range } else { start = mid + 1; // Search in the right half of the range } } return result; // Return the final result }; // Test the function with sample data const arr = [2, 4, 8, 2]; const K = 4; // Call the function and print the result const result = minimumSize(arr, K); console.log(result); |
2
Time Complexity: O(NlogN)
Auxiliary Space: O(1)