Problem Description

You have n retail stores and m different product types. Each product type has a certain quantity given in the array quantities, where quantities[i] represents how many items exist of product type i.

Your task is to distribute all products to the stores with these constraints:

• Each store can receive products from only one product type (but can receive any amount from that type)
• All products must be distributed
• You want to minimize the maximum number of products any single store receives

The goal is to find the smallest possible value x, where x is the maximum number of products given to any store after distribution.

Example Understanding: If you have quantities = [11, 6] and n = 6 stores:

• You could give the 11 items of type 1 to stores as: 4, 4, 3 (using 3 stores)
• You could give the 6 items of type 2 to stores as: 3, 3 (using 2 stores)
• Total stores used: 5 out of 6 available
• Maximum products in any store: 4
• This would give x = 4

The solution uses binary search to find the minimum possible maximum. The check function determines if it's possible to distribute all products such that no store gets more than x items. The expression (v + x - 1) // x calculates the minimum number of stores needed to distribute v items with at most x items per store (this is equivalent to ceil(v/x)). If the total stores needed is at most n, then x is feasible.

Intuition

The key insight is recognizing this as an optimization problem where we're trying to minimize the maximum value - a classic scenario for binary search on the answer.

Think about it this way: if we pick any value x as our maximum products per store, we can quickly check if it's possible to distribute all products without exceeding this limit. For each product type with quantity v, we need at least ceil(v/x) stores to distribute all v items with at most x items per store. If the total number of stores needed across all product types is at most n, then x is achievable.

Now, there's a monotonic property here: if we can distribute all products with maximum x items per store, we can definitely do it with x+1 items per store (we'd just need fewer stores). Conversely, if x doesn't work, neither will any value smaller than x.

This monotonic property makes binary search perfect. We search for the smallest x that works:

• The minimum possible x is 1 (each store gets at least 1 item if we use all stores)
• The maximum possible x is the largest quantity in our array (worst case: we put all items of one type in a single store)

For the feasibility check, the formula (v + x - 1) // x is a clever way to compute ceil(v/x) using integer arithmetic. This tells us how many stores we need to distribute v items with at most x items per store. We sum this across all product types and check if it's within our store limit n.

The binary search finds the boundary where the answer transitions from "not possible" to "possible", giving us the minimum feasible maximum.

Learn more about Greedy and Binary Search patterns.

Solution Approach

The solution implements a binary search to find the minimum possible maximum products per store.

Implementation Details:

1. Binary Search Setup: We use bisect_left from Python's bisect module to search in the range [1, 10^6]. The range starts at 1 (minimum possible products per store) and goes up to 10^6 (a reasonable upper bound for the maximum quantity).

2. Feasibility Check Function: The check(x) function determines if we can distribute all products with at most x items per store:

   def check(x):
       return sum((v + x - 1) // x for v in quantities) <= n

   • For each quantity v in quantities, we calculate (v + x - 1) // x
   • This formula computes ceil(v/x) using integer division, giving us the minimum number of stores needed for that product type
   • We sum the required stores for all product types
   • If the total is at most n, then x is feasible (returns True)

3. Binary Search Execution:

   return 1 + bisect_left(range(1, 10**6), True, key=check)

   • bisect_left finds the leftmost position where True can be inserted in the sorted sequence
   • The key=check parameter means we're searching based on the feasibility check
   • Since check(x) returns False for small values and True for large values, bisect_left finds the transition point
   • We add 1 to the result because bisect_left returns an index (0-based), but our range starts at 1

Why This Works:

• The check function creates a boolean sequence: [False, False, ..., False, True, True, ..., True]
• The transition from False to True happens at the minimum feasible x
• bisect_left efficiently finds this transition point in O(log(10^6)) time
• Each check takes O(m) time where m is the length of quantities
• Total time complexity: O(m * log(max_quantity))

Example Walkthrough

Let's walk through a concrete example with quantities = [15, 10, 10] and n = 7 stores.

Step 1: Set up binary search range

• Minimum possible x: 1 (each store gets at least 1 item)
• Maximum possible x: 15 (the largest quantity)
• We'll search in range [1, 15]

Step 2: Binary search iterations

Iteration 1: Try x = 8 (middle value)

• Product type 1 (15 items): needs ceil(15/8) = 2 stores (8 + 7)
• Product type 2 (10 items): needs ceil(10/8) = 2 stores (8 + 2)
• Product type 3 (10 items): needs ceil(10/8) = 2 stores (8 + 2)
• Total stores needed: 2 + 2 + 2 = 6 ≤ 7 ✓ (feasible)
• Since it works, try smaller values (search left half)

Iteration 2: Try x = 4 (middle of [1, 7])

• Product type 1 (15 items): needs ceil(15/4) = 4 stores (4 + 4 + 4 + 3)
• Product type 2 (10 items): needs ceil(10/4) = 3 stores (4 + 4 + 2)
• Product type 3 (10 items): needs ceil(10/4) = 3 stores (4 + 4 + 2)
• Total stores needed: 4 + 3 + 3 = 10 > 7 ✗ (not feasible)
• Since it doesn't work, try larger values (search right half)

Iteration 3: Try x = 6 (middle of [5, 7])

• Product type 1 (15 items): needs ceil(15/6) = 3 stores (6 + 6 + 3)
• Product type 2 (10 items): needs ceil(10/6) = 2 stores (6 + 4)
• Product type 3 (10 items): needs ceil(10/6) = 2 stores (6 + 4)
• Total stores needed: 3 + 2 + 2 = 7 ≤ 7 ✓ (feasible)
• Try smaller values

Iteration 4: Try x = 5

• Product type 1 (15 items): needs ceil(15/5) = 3 stores (5 + 5 + 5)
• Product type 2 (10 items): needs ceil(10/5) = 2 stores (5 + 5)
• Product type 3 (10 items): needs ceil(10/5) = 2 stores (5 + 5)
• Total stores needed: 3 + 2 + 2 = 7 ≤ 7 ✓ (feasible)
• Try smaller values one more time

Since x = 4 failed but x = 5 works, the answer is 5.

Final Distribution:

• Store 1: 5 items (type 1)
• Store 2: 5 items (type 1)
• Store 3: 5 items (type 1)
• Store 4: 5 items (type 2)
• Store 5: 5 items (type 2)
• Store 6: 5 items (type 3)
• Store 7: 5 items (type 3)

Maximum items in any store: 5 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * log(max(quantities))) where m is the length of the quantities array.

• The binary search using bisect_left searches over a range from 1 to 10^6, which takes O(log(10^6)) iterations.
• For each iteration of the binary search, the check function is called.
• The check function iterates through all elements in quantities to calculate the sum, which takes O(m) time.
• Therefore, the overall time complexity is O(m * log(10^6)) which simplifies to O(m * log(max(quantities))) since 10^6 is used as an upper bound for the maximum possible value.

Space Complexity: O(1)

• The check function uses only a constant amount of extra space for the sum calculation and loop variable.
• The bisect_left function with a range object doesn't create the entire range in memory; it generates values on-the-fly, using O(1) space.
• No additional data structures are created that scale with the input size.
• Therefore, the space complexity is O(1) excluding the input array itself.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Understanding of bisect_left Return Value

The most common pitfall is misunderstanding what bisect_left returns when used with a key function that produces a boolean sequence.

The Problem:

# Incorrect interpretation
result = bisect_left(range(1, 10**6), True, key=can_distribute)

Many assume this directly returns the minimum feasible value, but bisect_left returns an index into the range, not the actual value. Since range(1, 10**6) starts at 1, index 0 corresponds to value 1, index 1 to value 2, and so on.

The Fix:

# Correct: Add 1 to convert index to actual value
result = 1 + bisect_left(range(1, 10**6), True, key=can_distribute)

2. Using Wrong Search Bounds

Another pitfall is setting the upper bound too low or not considering edge cases.

The Problem:

# May fail if max(quantities) > 10000
result = 1 + bisect_left(range(1, 10000), True, key=can_distribute)

The Fix: Use either a safe upper bound or the actual maximum:

# Option 1: Safe upper bound
result = 1 + bisect_left(range(1, 10**6), True, key=can_distribute)

# Option 2: Exact bound (more efficient)
result = 1 + bisect_left(range(1, max(quantities) + 1), True, key=can_distribute)

3. Inverted Boolean Logic in Check Function

A subtle pitfall is inverting the boolean logic, searching for False instead of True.

The Problem:

def can_distribute(max_products):
    # Inverted: returns True when NOT feasible
    return sum((q + max_products - 1) // max_products for q in quantities) > n

# This creates sequence: [True, True, ..., False, False]
# bisect_left finds first False, but we want last True + 1

The Fix: Keep the logic straightforward - return True when the distribution is feasible:

def can_distribute(max_products):
    return sum((q + max_products - 1) // max_products for q in quantities) <= n

4. Integer Overflow in Ceiling Division

While less common in Python, the ceiling division formula can be confusing.

The Problem:

# Incorrect ceiling division attempts
stores_needed = v // x + (1 if v % x > 0 else 0)  # Verbose
stores_needed = math.ceil(v / x)  # Requires import, potential float precision issues

The Fix: Use the integer-only formula that's both efficient and precise:

stores_needed = (v + x - 1) // x  # Equivalent to ceil(v/x) using only integers