# 1283. Find the Smallest Divisor Given a Threshold

• Time: $O(n\log\max(\texttt{nums}))$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public: int smallestDivisor(vector& nums, int threshold) { int l = 1; int r = *max_element(begin(nums), end(nums)); while (l < r) { const int m = (l + r) / 2; if (sumDivision(nums, m) <= threshold) r = m; else l = m + 1; } return l; } private: int sumDivision(const vector& nums, int m) { int sum = 0; for (const int num : nums) sum += (num - 1) / m + 1; return sum; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int smallestDivisor(int[] nums, int threshold) { int l = 1; int r = Arrays.stream(nums).max().getAsInt(); while (l < r) { final int m = (l + r) / 2; if (sumDivision(nums, m) <= threshold) r = m; else l = m + 1; } return l; } private int sumDivision(int[] nums, int m) { int sum = 0; for (final int num : nums) sum += (num - 1) / m + 1; return sum; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution: def smallestDivisor(self, nums: List[int], threshold: int) -> int: l = 1 r = max(nums) while l < r: m = (l + r) // 2 if sum((num - 1) // m + 1 for num in nums) <= threshold: r = m else: l = m + 1 return l