Smallest Divisor Within a Threshold

Choose a positive whole number d. Divide every value of nums by d, round each result up to the next whole number, and add them. Return the smallest d for which that sum is at most threshold.

Examples

Example 1

Input:

smallest_divisor([1, 2, 5, 9], 6)

Output:

5

d = 5 gives 1 + 1 + 1 + 2 = 5, which is within 6, and d = 4 gives 1 + 1 + 2 + 3 = 7.

Example 2

Input:

smallest_divisor([44, 22, 33, 11, 1], 5)

Output:

44

Five values need threshold 5, so d must be the biggest value, 44.

Constraints

• 1 <= len(nums) <= 2 * 10**4
• len(nums) <= threshold <= 10**9
• 1 <= nums[i] <= 10**6
• Trying every divisor one by one is too slow for the large tests.