Find the Smallest Divisor Given a Threshold

Problem Id: 1283 Difficulty: Medium Tag: Binary Search


Intuition

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)).

Solution


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
            else:
                hi = mid
        return hi