1283. Find the Smallest Divisor Given a Threshold

Link

Solution

找到最小的滿足某個條件，且當n滿足此條件時n+1也會滿足 -> binary Search

滿足條件: n所造成的商和 <= threshold

  public int smallestDivisor(int[] nums, int threshold) {
        int min = 1;
        int max = 0;
        for(int num : nums){
            max = Math.max(max, num); 
        }
        
        while(max > min){
            int mid = min + (max-min)/2;
            if(isEnough(mid, nums, threshold)){
                max = mid;
            }else{
                min = mid+1;
            }
        }
        return min;
    }
    
    public boolean isEnough(int cur, int[] nums, int threshold){
        int total = 0;
        for(int num : nums){
            total += num/cur + (num%cur == 0 ? 0 : 1);
        }
        return total <= threshold;
    }