Welcome to Subscribe On Youtube
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 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 be given some number of products (possibly
0). Letxrepresent the maximum number of products given to any store. You wantxto 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.length1 <= m <= n <= 1051 <= quantities[i] <= 105
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 inO(Q)time whereQis the length ofquantities. kis in range[1, MAX(quantities)]and this answer range has perfect monotonicity: There must exist aKthat for everyk >= K, we can do the assignment withk; for everyk < 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; } }; -
class Solution: def minimizedMaximum(self, n: int, quantities: List[int]) -> int: left, right = 1, int(1e5) while left < right: mid = (left + right) >> 1 s = sum([(q + mid - 1) // mid for q in quantities]) if s <= n: right = mid else: left = mid + 1 return left ############ # 2064. Minimized Maximum of Products Distributed to Any Store # https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/ class Solution: def minimizedMaximum(self, n: int, quantities: List[int]) -> int: total = sum(quantities) def good(x): return sum(ceil(quantity / x) for quantity in quantities) <= n left, right = 1, max(quantities) while left < right: mid = left + (right - left) // 2 x = good(mid) if x: right = mid else: left = mid + 1 return left -
class Solution { public int minimizedMaximum(int n, int[] quantities) { int left = 1, right = (int) 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; } } -
func minimizedMaximum(n int, quantities []int) int { return 1 + sort.Search(1e5, func(x int) bool { x++ cnt := 0 for _, v := range quantities { cnt += (v + x - 1) / x } return cnt <= n }) } -
function minimizedMaximum(n: number, quantities: number[]): number { let left = 1; let right = 1e5; while (left < right) { const mid = (left + right) >> 1; let cnt = 0; for (const v of quantities) { cnt += Math.ceil(v / mid); } if (cnt <= n) { right = mid; } else { left = mid + 1; } } return left; }
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; } }; -
class Solution: def minimizedMaximum(self, n: int, quantities: List[int]) -> int: left, right = 1, int(1e5) while left < right: mid = (left + right) >> 1 s = sum([(q + mid - 1) // mid for q in quantities]) if s <= n: right = mid else: left = mid + 1 return left ############ # 2064. Minimized Maximum of Products Distributed to Any Store # https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/ class Solution: def minimizedMaximum(self, n: int, quantities: List[int]) -> int: total = sum(quantities) def good(x): return sum(ceil(quantity / x) for quantity in quantities) <= n left, right = 1, max(quantities) while left < right: mid = left + (right - left) // 2 x = good(mid) if x: right = mid else: left = mid + 1 return left -
class Solution { public int minimizedMaximum(int n, int[] quantities) { int left = 1, right = (int) 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; } } -
func minimizedMaximum(n int, quantities []int) int { return 1 + sort.Search(1e5, func(x int) bool { x++ cnt := 0 for _, v := range quantities { cnt += (v + x - 1) / x } return cnt <= n }) } -
function minimizedMaximum(n: number, quantities: number[]): number { let left = 1; let right = 1e5; while (left < right) { const mid = (left + right) >> 1; let cnt = 0; for (const v of quantities) { cnt += Math.ceil(v / mid); } if (cnt <= n) { right = mid; } else { left = mid + 1; } } return left; }
Discuss
https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/discuss/1563749/C%2B%2B-Binary-Search