Premium Only Content

2064. Minimized Maximum of Products Distributed to Any Store
You are given an integer n indicating there are n specialty retail stores. There are m product types of varying amounts, which are given as a 0-indexed integer array quantities, where quantities[i] represents the number of products of the ith product type.
You need to distribute all products to the retail stores following these rules:
A store can only be given at most one product type but can be given any amount of it.
After distribution, each store will have been given some number of products (possibly 0). Let x represent the maximum number of products given to any store. You want x to be as small as possible, i.e., you want to minimize the maximum number of products that are given to any store.
Return the minimum possible x.
Example 1:
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.
Example 2:
Input: n = 7, quantities = [15,10,10]
Output: 5
Explanation: One optimal way is:
- The 15 products of type 0 are distributed to the first three stores in these amounts: 5, 5, 5
- The 10 products of type 1 are distributed to the next two stores in these amounts: 5, 5
- The 10 products of type 2 are distributed to the last two stores in these amounts: 5, 5
The maximum number of products given to any store is max(5, 5, 5, 5, 5, 5, 5) = 5.
Example 3:
Input: n = 1, quantities = [100000]
Output: 100000
Explanation: The only optimal way is:
- The 100000 products of type 0 are distributed to the only store.
The maximum number of products given to any store is max(100000) = 100000.
Constraints:
m == quantities.length
1 <= m <= n <= 105
1 <= quantities[i] <= 105
class Solution {
public:
bool canDistribute(int x, vector<int>& quantities, int n) {
// Pointer to the first not fully distributed product type
int j = 0;
// Remaining quantity of the jth product type
int remaining = quantities[j];
// Loop through each store
for (int i = 0; i < n; i++) {
// Check if the remaining quantity of the jth product type
// can be fully distributed to the ith store
if (remaining <= x) {
// If yes, move the pointer to the next product type
j++;
// Check if all products have been distributed
if (j == quantities.size()) {
cout<<remaining<<" ";
return true;
} else {
remaining = quantities[j];
}
} else {
// Distribute the maximum possible quantity (x) to the ith store
remaining -= x;
}
}
return false;
}
int minimizedMaximum(int n, vector<int>& quantities) {
// Initialize the boundaries of the binary search
int left = 0;
int right = *max_element(quantities.begin(), quantities.end());
// Perform binary search until the boundaries converge
while (left < right) {
int middle = (left + right) / 2;
if (canDistribute(middle, quantities, n)) {
// Try for a smaller maximum
right = middle;
} else {
// Increase the minimum possible maximum
left = middle + 1;
}
}
return left;
}
};
-
9:00
The Art of Improvement
17 hours ago $2.37 earnedHow to Break Through Your Fear of Failure
7.8K2 -
7:18
DropItLikeItsScott
1 day ago $0.91 earnedWait, What...I Like GLOCK Now??
3.9K2 -
LIVE
Lofi Girl
2 years agoSynthwave Radio 🌌 - beats to chill/game to
1,114 watching -
2:32:02
Side Scrollers Podcast
18 hours agoPirateSoftware Situation, Twitch BANS mang0, “White Man Bad” CRASH OUT | Side Scrollers Live
45.7K9 -
14:17
GritsGG
14 hours agoCopy Our Strategy We Use to Win & Instantly Improve!
8.12K1 -
30:44
The Pascal Show
9 hours ago $2.49 earned‘I Was a Regular at the Freak Offs!’ — Adult Star Testifies in Diddy Trial
12K1 -
1:38:21
TruthStream with Joe and Scott
1 day agoC R Stewart Author of the Britfield book series live 6/26 3pm pacific 6pm Eastern
14.6K1 -
2:03:51
Inverted World Live
8 hours agoHypersonic Orbs Over New York | Ep. 66
81.3K26 -
3:09:47
TimcastIRL
10 hours agoGOP Rep Demands Citizenship STRIPPED From Dems Zohran Mamdani, NYC Mayor | Timcast IRL
439K264 -
1:21:31
Man in America
14 hours agoTech CEO Exposes the Diabolical Plan to ENSLAVE Us Through Smartphones
53K33