2064. Minimized Maximum of Products Distributed to Any Store

[mah-shamim]

Topics: Array, Binary Search

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 have been given some number of products (possibly 0). Let x represent the maximum number of products given to any store. You want x to 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.length
• 1 <= m <= n <= 105
• 1 <= quantities[i] <= 105

Hint:

1. There exists a monotonic nature such that when x is smaller than some number, there will be no way to distribute, and when x is not smaller than that number, there will always be a way to distribute.
2. If you are given a number k, where the number of products given to any store does not exceed k, could you determine if all products can be distributed?
3. Implement a function canDistribute(k), which returns true if you can distribute all products such that any store will not be given more than k products, and returns false if you cannot. Use this function to binary search for the smallest possible k.

[mah-shamim]

We can use a binary search on the maximum possible number of products assigned to any store (x). Here’s a step-by-step explanation and the PHP solution:

Approach

1. Binary Search Setup:

   • Set the lower bound (left) as 1 (since each store can get at least 1 product).
   • Set the upper bound (right) as the maximum quantity in quantities array (in the worst case, one store gets all products of a type).
   • Our goal is to minimize the value of x (maximum products given to any store).

2. Binary Search Logic:

   • For each mid-point x, check if it’s feasible to distribute all products such that no store has more than x products.
   • Use a helper function canDistribute(x) to determine feasibility.

3. Feasibility Check (canDistribute):

   • For each product type in quantities, calculate the minimum number of stores needed to distribute that product type without exceeding x products per store.
   • Sum the required stores for all product types.
   • If the total required stores is less than or equal to n, the distribution is possible with x as the maximum load per store; otherwise, it is not feasible.

4. Binary Search Adjustment:

   • If canDistribute(x) returns true, it means x is a feasible solution, but we want to minimize x, so adjust the right bound.
   • If it returns false, increase the left bound since x is too small.

5. Result:

   • Once the binary search completes, left will hold the minimum possible x.

Let's implement this solution in PHP: 2064. Minimized Maximum of Products Distributed to Any Store

<?php
/**
 * @param Integer $n
 * @param Integer[] $quantities
 * @return Integer
 */
function minimizedMaximum($n, $quantities) {    
    // Binary search on the possible values of `x`
    $left = 1;
    $right = max($quantities);
    
    while ($left < $right) {
        $mid = intval(($left + $right) / 2);
        
        if (canDistribute($mid, $quantities, $n)) {
            // If possible to distribute with `mid` as the maximum, try smaller values
            $right = $mid;
        } else {
            // Otherwise, increase `mid`
            $left = $mid + 1;
        }
    }
    
    return $left;
}

/**
 * Helper function to check if we can distribute products with maximum `x` per store
 *
 * @param $x
 * @param $quantities
 * @param $n
 * @return bool
 */
function canDistribute($x, $quantities, $n) {
   $requiredStores = 0;
   
   foreach ($quantities as $quantity) {
      // Calculate minimum stores needed for this product type
      $requiredStores += ceil($quantity / $x);
      // If we need more stores than available, return false
      if ($requiredStores > $n) {
          return false;
      }
   }
   
   return $requiredStores <= $n;
}

// Test cases
echo minimizedMaximum(6, [11, 6]); // Output: 3
echo minimizedMaximum(7, [15, 10, 10]); // Output: 5
echo minimizedMaximum(1, [100000]); // Output: 100000
?>

Explanation:

1. canDistribute function:

   • For each quantity, it calculates the minimum stores required by dividing the quantity by x (using ceil to round up since each store can get a whole number of products).
   • It returns false if the cumulative required stores exceed n.

2. Binary Search on x:

   • The binary search iteratively reduces the range for x until it converges on the minimal feasible value.

3. Efficiency:

   • This solution is efficient for large input sizes (n and m up to 10^5) because binary search runs in O(log(max_quantity) * m), which is feasible within the given constraints.

This approach minimizes x, ensuring the products are distributed as evenly as possible across the stores.

[basharul-siddike]

Thanks to solve this problem efficiently

[mah-shamim]

Thanks