# LC1283 - Find the Smallest Divisor Given a Threshold
## 线性关系 二分查找猜答案

class Solution {
    
    /*
    x: divisor
    f(x): f(x) = sum( (num[i] - 1) / x + 1 )
    */
    public int smallestDivisor(int[] nums, int threshold) {
        // sanity check
        // ...
        
        int length = nums.length;
        int minD = 1; // minDivisor
        int maxD = 0;
        for (int num : nums) {
            maxD = Math.max(maxD, num);
        }
        
        while (minD + 1 < maxD) {
            int midD = minD + (maxD - minD) / 2;
            if (canGetResultBy(midD, threshold, nums)) {
                maxD = midD;
            } else {
                minD = midD;
            }
        }

        // minimum
        if (canGetResultBy(minD, threshold, nums)) {
            return minD;
        }
        if (canGetResultBy(maxD, threshold, nums)) {
            return maxD;
        }
        return -1;
    }
    
    // inverse function
    // f(x) <= target --> right part
    // smallest x --> left point
    // boolean function == true --> in the right part --> shrink right bound
    private boolean canGetResultBy(int targetD, int targetThreshold, int[] nums) {
        int sum = 0;
        
        for (int num : nums) {
            sum += (num - 1) / targetD + 1;
            
            if (sum > targetThreshold) {
                return false;
            }
        }
        
        return true;
    }
}