< Back





1283. Find the Smallest Divisor Given a Threshold

We're asked to find the smallest divisor that we can divide all the numbers provided in the nums list
such that the sum of their quotients is less than or equal to the threshold.

We use binary search to discover this threshold, with the rightmost limit being the maximum number
provided in the nums list. During each iteration, we calculate the sum of the quotients with the
current selected divisor. Eventually, the leftmost limit of the search will be our answer.

The solution is as follows:


  from math import ceil

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

          while l <= r:
              m = (r + l) // 2
              t = sum([ceil(num / m) for num in nums])

              if t <= threshold:
                  r = m - 1
              else:
                  l = m + 1

          return l


_ Time Complexity:

  O(n log(k)) - Where k is the maximum number in the nums list, and n is the length of the nums list.

_ Space Complexity:

  O(1) - We use constant space to retain our variables.