Horje
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.
  • 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);

Output

2

Time Complexity: O(NlogN)
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Count number of ways array can be partitioned such that same numbers are present in same subarray Count number of ways array can be partitioned such that same numbers are present in same subarray
Find the lexicographically largest array containing all distinct elements from each prefix of the given array Find the lexicographically largest array containing all distinct elements from each prefix of the given array
Restore the original array from another array generated by given operations Restore the original array from another array generated by given operations
Reconstructing the Array with Maximum Possible Sum by Given Operations Reconstructing the Array with Maximum Possible Sum by Given Operations
Minimum number of operations to make maximum element of every subarray of size K at least X Minimum number of operations to make maximum element of every subarray of size K at least X

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 14



 

Horje