We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimized Maximum of Products Distributed to Any Store

Number: 2188

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Bloomberg, Salesforce, Siemens

Problem Description

Given n specialty retail stores and m product types with their respective quantities, distribute all products to the stores such that each store can receive products from at most one product type. The goal is to minimize the maximum number of products assigned to any store. Return this minimized maximum value.

Key Insights

  • Use binary search for the answer space. The lower bound is 1 and the upper bound is max(quantities).
  • For a guess value x, determine whether it’s possible to distribute each product type among stores so that no store gets more than x products.
  • For each product type with quantity q, the number of stores needed is ceil(q / x).
  • The candidate x is valid if the sum of stores required is less than or equal to n.

Space and Time Complexity

Time Complexity: O(m * log(max(quantities))) where m is the number of product types. Space Complexity: O(1) extra space (excluding input).

Solution

We approach the problem using binary search on the possible maximum number of products per store (x). The lower bound for x is 1 and the upper bound is the largest quantity from the input (since a store might need to hold all products of a type if only one store is used).

The main check is to see if a given x is feasible:

  • For each product type with quantity q, compute storesNeeded = ceil(q / x). This can be calculated using integer arithmetic: (q + x - 1) // x.
  • Sum these values across all product types. If the total is <= n (the number of stores), then x is a valid distribution limit.
  • Use binary search to find the minimal valid x.

This approach efficiently narrows down the answer by discarding ranges that are not possible based on the computed store requirements.

Code Solutions

def minimizedMax(n, quantities):
    # Function to check if a given max per store is feasible
    def canDistribute(x):
        requiredStores = 0
        for quantity in quantities:
            # Calculate required stores for this product type using ceil division
            requiredStores += (quantity + x - 1) // x
        return requiredStores <= n

    low, high = 1, max(quantities)
    # Binary search on possible maximum products per store
    while low < high:
        mid = (low + high) // 2
        # If mid is a valid distribution, try a smaller value
        if canDistribute(mid):
            high = mid
        else:
            low = mid + 1
    return low

# Example test
print(minimizedMax(6, [11, 6]))  # Expected output: 3
← Back to All Questions