[LeetCode] 2064. Minimized Maximum of Products Distributed to Any Store

 Problem : https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/

If X is valid answer, all numbers larger than X is still valid answer. If X is invalid answer, all numbers less than X is still invalid answer. We may use binary search to 'guess' the minimum valid answer.

class Solution {
    
    /**
     Use binary search to find the lower bound of the valid maximum number of products
     Time complexity = O ( N * Log(M) ).  
     N = number of product types. M = maximum value of the quantities
    */
    public int minimizedMaximum(int n, int[] quantities) {
        int right = Arrays.stream(quantities).max().getAsInt();
        int left = 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (isValid(n, quantities, mid)) {
                // 'mid' is a valid answer. any number larger than X is still valid answer.
                //  move the right pointer to left side.
                right = mid;
            } else {
                // 'mid' is a invalid answer. any number less than X is still invalid anwser.
                // move the left pointer to right side.
                left = mid + 1;
            }
        }
        
        return right;
    }
    
    /**
     'mx' is valid if all products can be distrbuted to 'n' stores.
    */
    boolean isValid(int n, int[] quantities, int mx) {
        int neededStore = 0;
        
        for (int i = 0; i < quantities.length; i++) {
            // accumulate the number of store needed for product type 'i'
            neededStore += quantities[i] / mx;
            neededStore += (quantities[i] % mx == 0) ? 0 : 1;
        }
       
        return neededStore <= n;
    }
}