Find the Smallest Divisor Given a Threshold

Problem Id: 1283 Difficulty: Medium Tag: Binary Search


The time complexity to calculate result for one divisor is t O(n). And based on the description, the divisor could be in [1, ..., max(nums)]. This is because when divisor >= max(nums), the result will always be len(nums).

So the brute force solution is to calculate the result for each i in [1, max(nums)]. And when the result is valid (result <= threshold), return it. In this case, the time complexity is O(n * m), where n is the length of nums and m is the maximum number in nums. This would be around (5 * 10 ^ 4) * (10 ^ 6) = 5 * 10 ^ 10 and would timeout.

One thing in this problem you need to notice is that, for all possible divisors, it would be always valid if it is greater than or equal to the result divisor. So for problems like this, we could use binary search. We had 2 variables lo and hi. We should keep hi a valid divisor, and lo always an invalid divisor. And each time, we either update lo to mid or hi to mid.

The time complexity of this binary search solution is O(n * lg(m)).


from math import ceil

class Solution:
    def upperSum(self, nums, divisor):
        return sum(ceil(num / divisor) for num in nums)

    def smallestDivisor(self, nums, threshold):
        lo = 1
        hi = max(nums)
        if sum(nums) <= threshold:
            return lo
        while hi - lo > 1:
            mid = (hi + lo) // 2
            if self.upperSum(nums, mid) > threshold:
                lo = mid
                hi = mid
        return hi