Distribute Product Types with the Smallest Store Cap
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
There are `n` stores and several product types. `quantities[i]` is the number of units of type `i`, and all units must be distributed. Each store can receive any number of units of at most one type; a store may also remain empty. Return the smallest possible value of the largest number of units assigned to any store.
```cpp
class Solution {
public:
int minimizedMaximum(int n, vector<int>& quantities);
};
```
### Examples
**Example 1:**
```text
n = 4, quantities = [7,3]
Output: 3
Explanation: Type counts can be split as 3,3,1 and 3; cap 2 would need six stores.
```
**Example 2:**
```text
n = 2, quantities = [4,9]
Output: 9
Explanation: Each type needs its own store, so neither can be split.
```
### Constraints
- `1 <= quantities.length <= n <= 10^5`.
- `1 <= quantities[i] <= 10^5`.
### Clarifying Questions
Types cannot be mixed inside one store. Empty stores are allowed, so a feasible assignment may use fewer than n stores.
```hint Inspect the structure
For a proposed cap x, how many stores are required by one product type?
```
### Reasoning checkpoints
- Distribute every unit while keeping different product types out of the same store.
- Show that the reported largest load is achievable and that a smaller one is impossible.
- Handle unused stores and a single large type without overlooking per-type restrictions.
### Optional extensions
Why is total quantity divided by n alone insufficient when stores cannot mix types?
Overview: Distribute Product Types with the Smallest Store Cap. Distribute all units of the product types in quantities among n stores. A store may receive units from at most one type and may be empty. Return the minimum possible maximum number of units received by any store.