Minimized Maximum of Products Distributed to Any Store

// Accepted solution for LeetCode #2064: Minimized Maximum of Products Distributed to Any Store
class Solution {
    public int minimizedMaximum(int n, int[] quantities) {
        int left = 1, right = (int) 1e5;
        while (left < right) {
            int mid = (left + right) >> 1;
            int cnt = 0;
            for (int v : quantities) {
                cnt += (v + mid - 1) / mid;
            }
            if (cnt <= n) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

// Accepted solution for LeetCode #2064: Minimized Maximum of Products Distributed to Any Store
func minimizedMaximum(n int, quantities []int) int {
	return 1 + sort.Search(1e5, func(x int) bool {
		x++
		cnt := 0
		for _, v := range quantities {
			cnt += (v + x - 1) / x
		}
		return cnt <= n
	})
}

# Accepted solution for LeetCode #2064: Minimized Maximum of Products Distributed to Any Store
class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        def check(x):
            return sum((v + x - 1) // x for v in quantities) <= n

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

// Accepted solution for LeetCode #2064: Minimized Maximum of Products Distributed to Any Store
/**
 * [2064] Minimized Maximum of Products Distributed to Any Store
 *
 * 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 i^th 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 <= 10^5
 * 	1 <= quantities[i] <= 10^5
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/
// discuss: https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn minimized_maximum(n: i32, quantities: Vec<i32>) -> i32 {
        0
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_2064_example_1() {
        let n = 6;
        let quantities = vec![11, 6];

        let result = 3;

        assert_eq!(Solution::minimized_maximum(n, quantities), result);
    }

    #[test]
    #[ignore]
    fn test_2064_example_2() {
        let n = 7;
        let quantities = vec![15, 10, 10];

        let result = 5;

        assert_eq!(Solution::minimized_maximum(n, quantities), result);
    }

    #[test]
    #[ignore]
    fn test_2064_example_3() {
        let n = 1;
        let quantities = vec![100000];

        let result = 100000;

        assert_eq!(Solution::minimized_maximum(n, quantities), result);
    }
}

// Accepted solution for LeetCode #2064: Minimized Maximum of Products Distributed to Any Store
function minimizedMaximum(n: number, quantities: number[]): number {
    let left = 1;
    let right = 1e5;
    while (left < right) {
        const mid = (left + right) >> 1;
        let cnt = 0;
        for (const v of quantities) {
            cnt += Math.ceil(v / mid);
        }
        if (cnt <= n) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}