1283 Find the Smallest Divisor Given a Threshold

Intuition

The problem is very similar infact identical to 875. Koko Eating Bananas. We need to minimize the divisor here, so that the condition stays true. The condition is that after dividing all the elements in the array, the sum of them all must be less than or equal to the threshold.

Code

Python3

def smallestDivisor(self, nums: List[int], threshold: int) -> int:
 
    left, right = 1, max(nums)
 
    while left < right:
        divisor = (left + right) // 2
 
        if sum([ceil(n / divisor) for n in nums]) <= threshold: # this divisor works for us
            right = divisor
        else:
            left = divisor + 1
 
 
    return left

Big O Analysis

• Runtime

  The runtime complexity here is $O(N\ast logK)$ since we are reducing our search space of size K in half (divisors) but for every divisor that we test - we also iterate the entire array of size N.

• Memory

  The memory usage is $O(1)$ since we are not using any extra data structure.

— A

GitHub | Twitter