Leetcode 2064: Minimized Maximum of Products Distributed to Any Store
You are given a number n representing the number of retail stores and an array of integers quantities. Each quantity[i] represents the number of products of the i-th product type available. The task is to distribute all the products to the stores in such a way that no store gets more than one product type, but may receive any quantity of that type. The goal is to minimize the maximum number of products assigned to any store. Return the smallest possible value of this maximum number of products assigned to a store.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer n followed by an array quantities representing the number of products available for each product type.
Example: Input: n = 5, quantities = [9, 5]
Constraints:
• 1 <= m <= n <= 10^5
• 1 <= quantities[i] <= 10^5
Output: Output the smallest possible value of the maximum number of products given to any store.
Example: Output: 3
Constraints:
• The result should be an integer representing the minimized maximum product distribution.
Goal: The objective is to find the minimum possible value of the maximum number of products assigned to any store.
Steps:
• 1. Set the initial range for the maximum number of products between 1 and the maximum quantity in the quantities array.
• 2. Use binary search to narrow down the possible values of the maximum product number, checking for feasibility by calculating how many stores are needed for each potential value.
• 3. Return the smallest value that works.
Goal: The input array can have up to 100,000 elements, and each quantity can be as large as 100,000.
Steps:
• n and m are within the range 1 <= n, m <= 10^5.
• Each quantity[i] is between 1 and 10^5.
Assumptions:
• The number of stores, n, is always greater than or equal to the number of product types, m.
• Products are distributed efficiently to minimize the maximum number assigned to any store.
• Input: Input: n = 5, quantities = [10, 5]
• Explanation: The best distribution of the 10 products of type 0 across 4 stores could be 3, 3, 2, 2, while the 5 products of type 1 could be distributed as 3, 2. The maximum number of products assigned to any store is 3.
• Input: Input: n = 6, quantities = [12, 8, 5]
• Explanation: The 12 products of type 0 can be distributed across 4 stores with amounts 3, 3, 3, 3. The 8 products of type 1 across 2 stores as 4, 4. The 5 products of type 2 across 2 stores as 3, 2. The maximum number of products assigned to any store is 4.
• Input: Input: n = 4, quantities = [5]
• Explanation: With only 5 products of type 0 and 4 stores, the maximum distribution to any store would be 2.
Approach: To solve this problem, we use binary search over the possible values of the maximum number of products per store. The main challenge is checking if a given maximum can be achieved given the constraints of how products can be distributed.
Observations:
• Binary search helps find the smallest possible value of the maximum number of products that any store receives.
• The total number of stores needed for a given maximum can be computed by distributing products optimally.
• This approach uses binary search to optimize the product distribution and minimize the maximum number of products assigned to any store.
Steps:
• Step 1: Initialize the binary search range. The minimum is 1, and the maximum is the largest quantity in the quantities array.
• Step 2: Perform binary search. For each middle value, check if it's feasible to assign products such that no store gets more than this number of products.
• Step 3: If it's feasible, update the result and continue searching for a smaller value. Otherwise, increase the middle value and continue the search.
Empty Inputs:
• There will always be at least one product type and one store, so empty inputs are not a concern.
Large Inputs:
• For large inputs, make sure the binary search approach runs efficiently within the time limits.
Special Values:
• If there is only one store, all products must go to that store.
Constraints:
• Ensure that the binary search approach works within the constraints of 10^5 stores and product quantities.
bool isPossible(vector<int>& qnty, int mid, int m, int n) {
int cnt = 0;
for(int i = 0; i < m; i++) {
if(qnty[i] <= mid) {
cnt++;
continue;
}
// if(mid == 1) cout << qnty[i];
int num = qnty[i];
cnt++;
while(num > mid) {
cnt++;
num -= mid;
}
}
// cout << mid << " " << cnt << " " << n << "\n";
return (cnt <= n);
}
int minimizedMaximum(int n, vector<int>& qnty) {
int m = qnty.size();
int ans = *max_element(qnty.begin(), qnty.end());
int l = 1, r = ans - 1;
while(l <= r) {
int mid = l + (r - l + 1) / 2;
// cout << mid << " ";
if(isPossible(qnty, mid, m, n)) {
// cout << mid << " ";
ans = mid;
r = mid - 1;
} else l = mid + 1;
}
return ans;
}
1 : Function Definition
bool isPossible(vector<int>& qnty, int mid, int m, int n) {
Define the 'isPossible' function, which checks if it's possible to partition the quantities into 'n' groups such that no group exceeds the value 'mid'.
2 : Variable Initialization
int cnt = 0;
Initialize the counter 'cnt' to 0, which tracks the number of partitions.
3 : Looping
for(int i = 0; i < m; i++) {
Start a loop that iterates through the quantities vector 'qnty'.
4 : Conditional Logic
if(qnty[i] <= mid) {
Check if the current quantity is less than or equal to the current 'mid' value.
5 : Increment
cnt++;
If the current quantity is less than or equal to 'mid', increment the count of partitions.
6 : Control Flow
continue;
Skip the rest of the loop and continue with the next iteration.
7 : Variable Assignment
int num = qnty[i];
Assign the current quantity to 'num' for further processing.
8 : Increment
cnt++;
Increment the count for the current quantity, as it will form at least one partition.
9 : Looping
while(num > mid) {
While the current quantity exceeds 'mid', keep breaking it down into smaller partitions.
10 : Increment
cnt++;
Increment the count for each partition formed by dividing the quantity 'num'.
11 : Mathematical Operation
num -= mid;
Reduce the quantity 'num' by 'mid', effectively partitioning it into smaller parts.
12 : Return Statement
return (cnt <= n);
Return true if the total number of partitions 'cnt' is less than or equal to 'n', indicating it's possible to partition the quantities accordingly.
13 : Function Definition
int minimizedMaximum(int n, vector<int>& qnty) {
Define the 'minimizedMaximum' function, which finds the minimized maximum of partitions for the given quantities.
14 : Variable Initialization
int m = qnty.size();
Initialize 'm' to the size of the quantities vector 'qnty'.
15 : Variable Assignment
int ans = *max_element(qnty.begin(), qnty.end());
Initialize 'ans' to the maximum quantity in the vector 'qnty'. This represents the starting point for the binary search.
16 : Binary Search Initialization
int l = 1, r = ans - 1;
Initialize the left ('l') and right ('r') bounds for the binary search.
17 : Binary Search Loop
while(l <= r) {
Start the binary search loop to find the minimized maximum partition.
18 : Binary Search Midpoint
int mid = l + (r - l + 1) / 2;
Calculate the midpoint 'mid' for the binary search to check if it's possible to partition the quantities accordingly.
19 : Conditional Logic
if(isPossible(qnty, mid, m, n)) {
Check if it's possible to partition the quantities with the current 'mid' value.
20 : Variable Assignment
ans = mid;
If partitioning is possible, update 'ans' to the current 'mid'.
21 : Binary Search Adjustment
r = mid - 1;
Adjust the right bound of the binary search to search for smaller possible values.
22 : Binary Search Adjustment
} else l = mid + 1;
If partitioning is not possible, adjust the left bound of the binary search to search for larger possible values.
23 : Return Statement
return ans;
Return the minimized maximum partition value found by the binary search.
Best Case: O(m * log(max(quantities)))
Average Case: O(m * log(max(quantities)))
Worst Case: O(m * log(max(quantities)))
Description: The binary search takes log(max(quantities)) iterations, and each check involves a linear scan over the quantities array (m), leading to an overall complexity of O(m * log(max(quantities))).
Best Case: O(m)
Worst Case: O(m)
Description: The space complexity is O(m) for storing the quantities array and performing the checks.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus