Minimized Maximum of Products Distributed to Any Store

Minimized Maximum of Products Distributed to Any Store - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 6, quantities = [11,6]

› Output: 3

💡 Note: With max 3 per store: Product type 0 needs ceil(11/3) = 4 stores, product type 1 needs ceil(6/3) = 2 stores. Total: 4 + 2 = 6 stores ≤ 6.

Example 2 — Single Product Type

$ Input: n = 7, quantities = [15]

› Output: 5

💡 Note: Only one product type with 15 units. With max 5 per store: ceil(15/5) = 3 stores ≤ 7. With max 4: ceil(15/4) = 4 stores ≤ 7. With max 3: ceil(15/3) = 5 stores ≤ 7. With max 2: ceil(15/2) = 8 stores > 7.

Example 3 — Multiple Small Quantities

$ Input: n = 1, quantities = [100000]

› Output: 100000

💡 Note: Only 1 store available, so it must take all 100000 products of the single type.

Constraints

m == quantities.length
1 ≤ m ≤ n ≤ 10⁵
1 ≤ quantities[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

n=6 stores, quantities=[11,6] product types

Distribution

Find minimum possible maximum per store

Output

Minimum maximum = 3

Key Takeaway

🎯 Key Insight: We can binary search on the answer space because if maximum x works, then any larger maximum also works

Asked in

G Google 15 A Amazon 12 M Microsoft 8

The key insight is to binary search on the answer space - the maximum number of products any store can receive. We can check if a given maximum works by calculating how many stores each product type needs (using ceiling division) and ensuring the total doesn't exceed n. Best approach is binary search on answer space with Time: O(log(max) × m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search on Answer	O(max(quantities) × m)	O(1)	Try every possible maximum from 1 upward until we find one that works
Binary Search on Answer Space	O(log(max(quantities)) × m)	O(1)	Binary search on the possible maximum values to find the minimum one that works

Linear Search on Answer — Algorithm Steps

Step 1: Try x = 1, 2, 3, ... until max(quantities)
Step 2: For each x, calculate stores needed for each product type
Step 3: Return first x where total stores ≤ n

Visualization

Tap to expand

Step-by-Step Walkthrough

Try x=1

Check if we can distribute with max 1 per store

Try x=2

If x=1 fails, try max 2 per store

Continue

Keep increasing until we find working maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int canDistribute(int maxPerStore, int n, int* quantities, int size) {
    int storesNeeded = 0;
    for (int i = 0; i < size; i++) {
        storesNeeded += (quantities[i] + maxPerStore - 1) / maxPerStore; // Ceiling division
    }
    return storesNeeded <= n;
}

int solution(int n, int* quantities, int size) {
    int maxQty = 0;
    for (int i = 0; i < size; i++) {
        if (quantities[i] > maxQty) {
            maxQty = quantities[i];
        }
    }
    
    // Try every possible maximum from 1 upward
    for (int x = 1; x <= maxQty; x++) {
        if (canDistribute(x, n, quantities, size)) {
            return x;
        }
    }
    
    return maxQty;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %s", line);
    
    // Parse array manually
    int quantities[1000];
    int size = 0;
    char* ptr = line + 1; // Skip opening bracket
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        quantities[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(n, quantities, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(max(quantities) × m)

Try each possible max from 1 to max(quantities), for each check all m product types

✓ Linear Growth

Space Complexity

O(1)

Only using variables, no extra data structures

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler