Formatted question description: https://leetcode.ca/all/2064.html

# 2064. Minimized Maximum of Products Distributed to Any Store (Medium)

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 `i`

product type.^{th}

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 be 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:3Explanation: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:5Explanation: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:100000Explanation: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 <= 10`

^{5}`1 <= quantities[i] <= 10`

^{5}

**Similar Questions**:

- Koko Eating Bananas (Medium)
- Capacity To Ship Packages Within D Days (Medium)
- Find the Smallest Divisor Given a Threshold (Medium)
- Magnetic Force Between Two Balls (Medium)
- Minimum Limit of Balls in a Bag (Medium)

## Solution 1. Binary Search

**Intuition**:

- Given
`k`

(the maximum number of products given to any store), we can compute the number of stores we are able to assign in`O(Q)`

time where`Q`

is the length of`quantities`

. `k`

is in range`[1, MAX(quantities)]`

and this answer range has perfect monotonicity: There must exist a`K`

that for every`k >= K`

, we can do the assignment with`k`

; for every`k < K`

, we can’t do the assignment because the number of stores are not enough.

So, we can use binary search to find this `K`

in `O(Qlog(MAX(quantities)))`

time.

```
// OJ: https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/
// Time: O(QlogM) where `Q` is the length of `quantities` and `M` is the max element in `quantities`.
// Space: O(1)
class Solution {
public:
int minimizedMaximum(int n, vector<int>& Q) {
long long L = 1, R = accumulate(begin(Q), end(Q), 0LL);
auto valid = [&](int M) {
int ans = 0;
for (int n : Q) ans += (n + M - 1) / M; // ceil(n / M)
return ans <= n;
};
while (L <= R) {
long long M = (L + R) / 2;
if (valid(M)) R = M - 1;
else L = M + 1;
}
return L;
}
};
```

Or use `L < R`

template

```
// OJ: https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/
// Time: O(QlogM) where `Q` is the length of `quantities` and `M` is the max element in `quantities`.
// Space: O(1
class Solution {
public:
int minimizedMaximum(int n, vector<int>& Q) {
long long L = 1, R = *max_element(begin(Q), end(Q));
auto valid = [&](int M) {
int ans = 0;
for (int n : Q) {
ans += (n + M - 1) / M;
}
return ans <= n;
};
while (L < R) {
long long M = (L + R) / 2;
if (valid(M)) R = M;
else L = M + 1;
}
return L;
}
};
```

## Discuss

https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/discuss/1563749/C%2B%2B-Binary-Search