Find the Smallest Divisor Given a Threshold

To solve this problem, we can use a binary search algorithm. The smallest divisor is clearly 1 and the maximum divisor is the maximum number in the array, because the sum of the array divided by 1 is the maximum and will decrease as the divisor increases. The sum reaches its minimum when the divisor is the maximum number in the array.

The binary search will start from these two boundaries and find the middle point. Then it calculates the sum of the array divided by the middle point. If the sum is less than the threshold, it means the divisor is too large, so it sets the end boundary to the middle point. If the sum is larger than the threshold, it means the divisor is too small, so it sets the start boundary to the middle point + 1. The search continues until the start and end boundaries meet, which will be the smallest divisor.

Here is the Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from math import ceil

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        start, end = 1, max(nums)

        while start < end:
            mid = (start + end) // 2
            if sum(ceil(num / mid) for num in nums) > threshold:
                start = mid + 1
            else:
                end = mid

        return start

This works in O(N log M) time, where N is the size of the array and M is the max number in the array. The binary search takes log M iterations and for each iteration we sum the array which takes N operations. The space complexity is O(1) as we only need a few variables to store the boundaries and the mid point.