# Minimized Maximum of Products Distributed to Any Store
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store)
Canonical: https://scaleengineer.com/dsa/problems/minimized-maximum-of-products-distributed-to-any-store
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Siemens](https://scaleengineer.com/companies/siemens)
---
## Problem
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`

# Approaches
## Brute Force with Linear Search
This approach involves checking every possible value for the maximum number of products `x` in a store, starting from 1. For each value of `x`, we determine if it's possible to distribute all products among the `n` stores without any store exceeding `x` products. The first value of `x` for which this is possible is the minimized maximum.
**Time:** O(m * K), where `m` is the number of product types (`quantities.length`) and `K` is the maximum value in `quantities`. The outer loop runs up to `K` times, and the inner check takes `O(m)` time. · **Space:** O(1), as we only use a few variables to store state.
**Pros:** Simple to understand and implement.; Guaranteed to find the correct answer.
**Cons:** Very slow and will time out on larger test cases due to its linear scan over a potentially large range of answers.
### Explanation
The problem asks to find the minimum possible value of `x`, where `x` is the maximum number of products given to any store.
The smallest possible value for `x` is 1. The largest possible value for `x` is the maximum quantity in the `quantities` array, as in the worst case, a single store might have to take all products of a certain type.
We can iterate through each possible value of `x` from 1 upwards. For each `x`, we check if it's a feasible maximum.
To check if a given `x` is feasible, we calculate the total number of stores required. For a product type with `q` items, if each store can hold at most `x` items, we need `ceil(q / x)` stores. In integer arithmetic, this is calculated as `(q + x - 1) / x`.
We sum up the required stores for all product types. If this total is less than or equal to the available stores `n`, then `x` is a feasible maximum.
Since we are checking `x` in increasing order (1, 2, 3, ...), the first `x` that we find to be feasible will be the minimum possible value.
This approach is simple to understand but inefficient for large inputs.

```java
class Solution {
    public int minimizedMaximum(int n, int[] quantities) {
        int maxQuantity = 0;
        for (int q : quantities) {
            maxQuantity = Math.max(maxQuantity, q);
        }

        for (int x = 1; x <= maxQuantity; x++) {
            if (canDistribute(n, quantities, x)) {
                return x;
            }
        }
        return maxQuantity; // Should not be reached if constraints are met
    }

    private boolean canDistribute(int n, int[] quantities, int x) {
        long storesNeeded = 0;
        for (int q : quantities) {
            storesNeeded += (q + x - 1) / x;
        }
        return storesNeeded <= n;
    }
}
```
### Algorithm
- Find the maximum quantity `max_q` in the `quantities` array.
- Iterate through possible answers `x` from `1` to `max_q`.
- For each `x`, calculate the total number of stores required.
    - Initialize `stores_needed = 0`.
    - For each `quantity` `q` in `quantities`:
        - `stores_needed += ceil(q / x)`, which is `(q + x - 1) / x`.
- If `stores_needed` is less than or equal to `n`, then `x` is a valid solution. Since we are iterating from the smallest possible `x`, this is the minimum possible maximum. Return `x`.

## Binary Search on the Answer
This problem has a monotonic property that makes it suitable for binary search. If we can distribute all products with a maximum of `x` items per store, we can also do it with any maximum greater than `x`. This allows us to binary search for the smallest possible value of `x` in the range of possible answers.
**Time:** O(m * log K), where `m` is the number of product types (`quantities.length`) and `K` is the maximum value in `quantities`. The binary search takes `O(log K)` iterations, and each iteration involves a check that takes `O(m)` time. · **Space:** O(1), as the algorithm uses a constant amount of extra space.
**Pros:** Highly efficient, significantly faster than the brute-force approach.; Optimal solution for the given constraints.
**Cons:** Slightly more complex to conceptualize than a direct brute-force approach.
### Explanation
The core idea is to search for the answer `x` (the minimized maximum) instead of constructing the distribution. The range of possible answers for `x` is from 1 to `max(quantities)`.
We can define a function `canDistribute(x)` that returns `true` if it's possible to distribute all products with `x` as the maximum per store, and `false` otherwise.
The `canDistribute(x)` function works by calculating the total number of stores required for a given `x`. For each product quantity `q`, the number of stores needed is `ceil(q / x)`, which can be calculated as `(q + x - 1) / x`. We sum these values for all quantities. If the total number of stores needed is not more than `n`, then `canDistribute(x)` is `true`.
The property we leverage is: if `canDistribute(x)` is true, then `canDistribute(x+1)` is also true. This creates a monotonic sequence of `false, false, ..., true, true` for the `canDistribute` function over the range of `x`, allowing us to use binary search to find the first `true` value, which corresponds to the minimum `x`.
The binary search algorithm is as follows:
- Set the search range: `low = 1`, `high = max(quantities)`.
- Initialize a variable `ans` to store the best possible answer, e.g., `ans = high`.
- While `low <= high`:
    - Calculate `mid = low + (high - low) / 2`.
    - If `canDistribute(mid)` is true:
        - `mid` is a potential answer. We try to find an even smaller one.
        - So, we record `mid` as our current best answer (`ans = mid`) and search in the lower half (`high = mid - 1`).
    - Else (`canDistribute(mid)` is false):
        - `mid` is too small to be a valid maximum. We need to allow stores to take more items.
        - We search in the upper half (`low = mid + 1`).
- After the loop, `ans` will hold the minimized maximum.

```java
class Solution {
    public int minimizedMaximum(int n, int[] quantities) {
        int low = 1;
        int high = 0;
        for (int q : quantities) {
            high = Math.max(high, q);
        }

        int ans = high;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (mid == 0) { // Avoid division by zero, though low starts at 1
                low = 1;
                continue;
            }
            
            if (canDistribute(n, quantities, mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private boolean canDistribute(int n, int[] quantities, int x) {
        long storesNeeded = 0;
        for (int q : quantities) {
            storesNeeded += (long)(q + x - 1) / x;
        }
        return storesNeeded <= n;
    }
}
```
### Algorithm
- Define the search space for the answer `x`. The lower bound `low` is 1, and the upper bound `high` is the maximum value in `quantities`.
- Perform a binary search on this range `[low, high]`.
- In each step of the binary search, pick a `mid` value.
- Check if it's possible to distribute all products with `mid` as the maximum per store. This is done by a helper function `canDistribute(mid)`.
    - `canDistribute(mid)` calculates the total stores needed: `sum(ceil(q / mid))` for all `q` in `quantities`.
    - It returns `true` if the total stores needed is `<= n`, `false` otherwise.
- If `canDistribute(mid)` is `true`, it means `mid` is a possible answer. We try for a smaller answer, so we update `ans = mid` and set `high = mid - 1`.
- If `canDistribute(mid)` is `false`, `mid` is too small. We need a larger maximum, so we set `low = mid + 1`.
- The loop continues until `low > high`, and the final value of `ans` is the minimized maximum.

# Solutions
### Java

```java
class Solution {
public
  int minimizedMaximum(int n, int[] quantities) {
    int left = 1, right = (int)1 e5;
    while (left < right) {
      int mid = (left + right) >> 1;
      int cnt = 0;
      for (int v : quantities) {
        cnt += (v + mid - 1) / mid;
      }
      if (cnt <= n) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimizedMaximum(int n, vector<int> &quantities) {
    int left = 1, right = 1e5;
    while (left < right) {
      int mid = (left + right) >> 1;
      int cnt = 0;
      for (int &v : quantities) {
        cnt += (v + mid - 1) / mid;
      }
      if (cnt <= n) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
};

```

### Python

```python
class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int: def check(x): return sum((v + x - 1) // x for v in quantities) <= n return 1 + bisect_left(range(1, 10 ** 6), True, key=check)

```