Minimized maximum of Products distributed to any store
Given N shopkeepers and an array quantities[], where quantities[i] = number of products of type i. All the products need to be distributed among N shopkeepers such that each shopkeeper can have at most one type of product of any quantity possibly 0. The task is to minimize the maximum number of products that are given to any shopkeeper.
Examples:
Input: n = 6, quantities[] = {11,6}
Output: 3
Explanation: One optimal way is:-
-The 11 products of type 0 are distributed to the first four stores in these amounts: 2, 3, 3, 3
-The 6 products of type 1 are distributed to the other two stores in these amounts: 3, 3
The maximum number of products given to any store is max(2, 3, 3, 3, 3, 3) = 3.Input: n = 1 , quantities[] = {500}
Output: 500
Explanation : The 500 products of type 0 are distributed to the first store.
Approach: To solve the problem follow the below idea.
This problem can be solved using the Binary Search. We know that binary search can be used when any parameter is monotonically increasing here in this case we can apply the binary search on the quantity parameter with low = 0 and high = max quantity.
Steps to solve the problem:
- Initialize low = 0, high = max quantity, and max_dist to store the result.
- Perform binary search while low <=high
- Check if choosing mid value as quantity to be distributed to each shop, in the validDistribution() traverse the quantities array and see how many shops the mid quantity can be distributed to it should not be > n.
- If the mid value is valid minimize the mid-value and store it in max_dist, change the high to mid-1
- Else if the mid value is invalid change the low to mid+1.
- Return the max_dist
Implementation for the above approach:
C++
#include <bits/stdc++.h> using namespace std; bool isValidDistributionCheck( int n, int mid, vector< int > quantities) { // Traverse the quantities array and see how many shops // the mid quantity can be distributed it should not be // > n for ( int i = 0; i < quantities.size(); i++) { if (quantities[i] % mid == 0) n -= (quantities[i] / mid); else n -= ((quantities[i] / mid) + 1); } // Return true if valid return n >= 0; } int maximizedMinumumQuantity( int n, vector< int > quantities) { // Initialize low as 0 and high as max quantity on the // vector and max_dist to store the result. int low = 1; int high = *max_element(quantities.begin(), quantities.end()); // Result int max_dis = INT_MAX; // Perform binary search while low <=high while (low <= high) { int mid = low + (high - low) / 2; // If mid value is valid minimize the mid value and // store it in max_dist, change the high to mid-1 if (isValidDistributionCheck(n, mid, quantities)) { max_dis = min(mid, max_dis); high = mid - 1; } // Else if the mid value is invalid change the low // to mid+1. else { low = mid + 1; } } // Return the max_dist if (max_dis == INT_MAX) return -1; return max_dis; } // Driver code int main() { vector< int > quantities = { 11, 6 }; int n = 6; cout << maximizedMinumumQuantity(n, quantities); return 0; } |
Java
// Java Implementation import java.util.*; public class MaximizedMinimumQuantity { // Function to check if the mid value is a valid distribution static boolean isValidDistributionCheck( int n, int mid, List<Integer> quantities) { // Traverse the quantities array and see how many shops // the mid quantity can be distributed; it should not be > n for ( int i = 0 ; i < quantities.size(); i++) { if (quantities.get(i) % mid == 0 ) n -= (quantities.get(i) / mid); else n -= ((quantities.get(i) / mid) + 1 ); } // Return true if valid return n >= 0 ; } // Function to find the maximized minimum quantity static int maximizedMinimumQuantity( int n, List<Integer> quantities) { // Initialize low as 1 and high as max quantity in the vector // and max_dist to store the result. int low = 1 ; int high = Collections.max(quantities); // Result int max_dis = Integer.MAX_VALUE; // Perform binary search while low <= high while (low <= high) { int mid = low + (high - low) / 2 ; // If mid value is valid, minimize the mid value and // store it in max_dist, change the high to mid-1 if (isValidDistributionCheck(n, mid, quantities)) { max_dis = Math.min(mid, max_dis); high = mid - 1 ; } // Else if the mid value is invalid, change the low to mid+1. else { low = mid + 1 ; } } // Return the max_dist if (max_dis == Integer.MAX_VALUE) return - 1 ; return max_dis; } // Driver code public static void main(String[] args) { List<Integer> quantities = Arrays.asList( 11 , 6 ); int n = 6 ; System.out.println(maximizedMinimumQuantity(n, quantities)); } } // This code is contributed by Tapesh(tapeshdua420) |
Python3
def is_valid_distribution_check(n, mid, quantities): # Traverse the quantities array and see how many shops # the mid quantity can be distributed, it should not be > n for i in range ( len (quantities)): if quantities[i] % mid = = 0 : n - = quantities[i] / / mid else : n - = (quantities[i] / / mid) + 1 # Return true if valid return n > = 0 def maximized_minimum_quantity(n, quantities): # Initialize low as 0 and high as max quantity in the # vector and max_dist to store the result. low = 1 high = max (quantities) # Result max_dis = float ( 'inf' ) # Perform binary search while low <= high while low < = high: mid = low + (high - low) / / 2 # If mid value is valid, minimize the mid value and # store it in max_dist, change the high to mid-1 if is_valid_distribution_check(n, mid, quantities): max_dis = min (mid, max_dis) high = mid - 1 # Else if the mid value is invalid, change the low # to mid+1. else : low = mid + 1 # Return the max_dist if max_dis = = float ( 'inf' ): return - 1 return max_dis # Driver code if __name__ = = "__main__" : quantities = [ 11 , 6 ] n = 6 print (maximized_minimum_quantity(n, quantities)) |
C#
using System; using System.Collections.Generic; using System.Linq; class GFG { static bool IsValidDistributionCheck( int n, int mid, List< int > quantities) { // Traverse the quantities array and see how many shops // the mid quantity can be distributed; it should not be // greater than n. foreach ( int quantity in quantities) { if (quantity % mid == 0) n -= (quantity / mid); else n -= ((quantity / mid) + 1); } // Return true if valid return n >= 0; } static int MaximizedMinumumQuantity( int n, List< int > quantities) { // Initialize low as 0 and high as max quantity in the // list and max_dis to store the result. int low = 1; int high = quantities.Max(); // Result int max_dis = int .MaxValue; // Perform binary search while low <= high while (low <= high) { int mid = low + (high - low) / 2; // If mid value is valid, minimize the mid value and // store it in max_dist, change the high to mid-1. if (IsValidDistributionCheck(n, mid, quantities)) { max_dis = Math.Min(mid, max_dis); high = mid - 1; } // Else if the mid value is invalid, change the low // to mid+1. else { low = mid + 1; } } // Return the max_dist if (max_dis == int .MaxValue) return -1; return max_dis; } // Driver code static void Main( string [] args) { List< int > quantities = new List< int > { 11, 6 }; int n = 6; Console.WriteLine(MaximizedMinumumQuantity(n, quantities)); } } |
Javascript
// Javascript Implementation // Function to check if a given mid quantity is a valid distribution function isValidDistributionCheck(n, mid, quantities) { for (let i = 0; i < quantities.length; i++) { if (quantities[i] % mid === 0) { n -= quantities[i] / mid; } else { n -= Math.floor(quantities[i] / mid) + 1; } } return n >= 0; } // Function to maximize the minimum quantity function maximizedMinimumQuantity(n, quantities) { let low = 1; let high = Math.max(...quantities); let max_dis = Infinity; while (low <= high) { let mid = low + Math.floor((high - low) / 2); if (isValidDistributionCheck(n, mid, quantities)) { max_dis = Math.min(mid, max_dis); high = mid - 1; } else { low = mid + 1; } } if (max_dis === Infinity) { return -1; } return max_dis; } // Driver code const quantities = [11, 6]; const n = 6; console.log(maximizedMinimumQuantity(n, quantities)); // This code is contributed by Tapesh(tapeshdua420) |
3
Time Complexity: O(M * log N) where M is the size of the array and N is the max value in the array.
Auxiliary Space: O(1)
Contact Us