Minimized Maximum of Products Distributed to Any Store

Leetcode Problem:

• Minimized Maximum of Products Distributed to Any Store

Summary

• This problem requires finding the minimum possible maximum number of products given to any store when distributing products to specialty retail stores.

Approach

• The solution uses a binary search approach to find the minimum possible maximum number of products
• It starts by initializing two pointers, one at 1 and one at 100000, and then iteratively calculates the midpoint
• It then checks if the maximum number of products that can be given to each store is less than or equal to the total number of stores
• If it is, it updates the right pointer and the answer; otherwise, it updates the left pointer.

Complexity

• O(m log max(quantities[i]))

Explanation

• The solution works by using a binary search approach to find the minimum possible maximum number of products
• It starts by initializing two pointers, one at 1 and one at 100000, and then iteratively calculates the midpoint
• It then checks if the maximum number of products that can be given to each store is less than or equal to the total number of stores
• If it is, it updates the right pointer and the answer; otherwise, it updates the left pointer
• This approach ensures that the solution is efficient and can handle large inputs.

Solution Code:

class Solution {
public:
    int minimizedMaximum(int n, vector& quantities) {
        int ans = quantities[0];
        int l = 1;
        int r = 100000;
        while(l <= r){
            int mid = (l + r) / 2;
            int cnt = 0;
            for(int i = 0 ; i < quantities.size(); i++){
                cnt += quantities[i] / mid;
                if (quantities[i] % mid != 0){
                    cnt++;
                }
            }
            if (cnt <= n){
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
};