2064. Minimized Maximum of Products Distributed to Any Store LeetCode Solution
In this guide, you will get 2064. Minimized Maximum of Products Distributed to Any Store LeetCode Solution with the best time and space complexity. The solution to Minimized Maximum of Products Distributed to Any Store problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
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
Complexity Analysis
Time Complexity: O(n\log(\max(\texttt{quantities})))
Space Complexity: O(1)
2064. Minimized Maximum of Products Distributed to Any Store LeetCode Solution in C++
class Solution {
public:
int minimizedMaximum(int n, vector<int>& quantities) {
int l = 1;
int r = ranges::max(quantities);
while (l < r) {
const int m = (l + r) / 2;
if (numStores(quantities, m) <= n)
r = m;
else
l = m + 1;
}
return l;
}
private:
int numStores(const vector<int>& quantities, int m) {
// ceil(q / m)
return accumulate(
quantities.begin(), quantities.end(), 0,
[&](int subtotal, int q) { return subtotal + (q - 1) / m + 1; });
}
}; /* code provided by PROGIEZ */
2064. Minimized Maximum of Products Distributed to Any Store LeetCode Solution in Java
class Solution {
public int minimizedMaximum(int n, int[] quantities) {
int l = 1;
int r = Arrays.stream(quantities).max().getAsInt();
while (l < r) {
final int m = (l + r) / 2;
if (numStores(quantities, m) <= n)
r = m;
else
l = m + 1;
}
return l;
}
private int numStores(int[] quantities, int m) {
// ceil(q / m)
return Arrays.stream(quantities).reduce(0, (subtotal, q) -> subtotal + (q - 1) / m + 1);
}
} // code provided by PROGIEZ
2064. Minimized Maximum of Products Distributed to Any Store LeetCode Solution in Python
class Solution:
def minimizedMaximum(self, n: int, quantities: list[int]) -> int:
l = 1
r = max(quantities)
def numStores(m: int) -> int:
return sum((q - 1) // m + 1 for q in quantities)
while l < r:
m = (l + r) // 2
if numStores(m) <= n:
r = m
else:
l = m + 1
return l # code by PROGIEZ
