Minimized maximum of products distributed to any store

Array Binary Search Greedy

63.0% acceptance

Feb 25, 2026

1820

107

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimized_maximum(n: i32, quantities: Vec<i32>) -> i32 {
    let can_do = |x: i32| -> bool {
      // total stores needed = sum(ceil(q/x) for q in quantities)
      let total: i64 = quantities.iter().map(|&q| ((q as i64 + x as i64 - 1) / x as i64)).sum();
      total <= n as i64
    };
    let mut lo = 1i32;
    let mut hi = *quantities.iter().max().unwrap();
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      if can_do(mid) {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo
  }
}