# 1283. Find the Smallest Divisor Given a Threshold
#### Difficulty: Medium
link: https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/

### 1. Binary Search
#### $O(n log\ max(nums))$ runtime, $O(1)$ space

divisor上下限為1到nums的最大值，用Binary search模板來尋找滿足題目要求條件的最小值。

##### python

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def feasible(divisor):
            return sum(math.ceil(n / divisor) for n in nums) <= threshold
        
        left, right = 1, max(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

Early Return和ceil優化

        def feasible(divisor):
            total = 0
            for n in nums:
                total += (n - 1) // divisor + 1
                if total > threshold:
                    return False
            return True

###### tags: `leetcode`