Find the Smallest Divisor Given a Threshold | Leetcode 1283

The “Find the Smallest Divisor Given a Threshold” problem is a classic binary search question that helps you practice optimization under constraints.

In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.

Here’s the [Problem Link] to begin with.

Given an array of integers nums and an integer threshold, we will choose a positive integer divisor, divide all the array by it, and sum the division’s result. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.

Each result of the division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).

The test cases are generated so that there will be an answer.

Example 1:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2). 

Example 2:

Input: nums = [44,22,33,11,1], threshold = 5
Output: 44

Constraints:

• 1 <= nums.length <= 5 * 104
• 1 <= nums[i] <= 106
• nums.length <= threshold <= 106

Brute Force Solution (Try Every Possible Divisor)

Intuition and Approach

Let’s solve the problem in the most straightforward way:

1. Try Every Divisor:
   Try every possible divisor from 1 up to the largest number in the array.
2. Check If It Meets the Threshold:
   For each divisor, calculate the total sum (rounded up for each element). If the sum is within the threshold, return the divisor.
3. Why does this work?
   We check every possible divisor, so we’re sure to find the smallest one that works.

This approach is easy to understand but not efficient for large numbers.

Code Implementation

import math
from typing import List

class Solution:
    def getThreshold(self, x, nums, threshold):
        total = 0
        for num in nums:
            total += math.ceil(num / x)    # Divide and round up for each element
        return total <= threshold

    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        max_num = max(nums)
        for divisor in range(1, max_num + 1):   # Try every possible divisor
            if self.getThreshold(divisor, nums, threshold):
                return divisor                  # Return the first valid divisor
        return max_num

Code Explanation

• For each divisor from 1 to the maximum number in the array, check if the sum is within the threshold.
• Use a helper function to calculate the total sum for a given divisor.
• Return the first divisor that satisfies the condition.

Dry Run

Input:
nums = [1], threshold = 6

• divisor = 1:  → sum = 17 (too high)
• divisor = 2:  → sum = 10 (too high)
• divisor = 3:  → sum = 7 (too high)
• divisor = 4:  → sum = 7 (too high)
• divisor = 5:  → sum = 5 (valid, return 5)

Final Output:
5

Time and Space Complexity

• Time Complexity: O(max(nums) * n)
  For each divisor, we check all elements.
• Space Complexity: O(1)
  Only variables for counting.

Conclusion

The brute force approach is simple and works for small inputs, but it’s too slow for large values.

Optimal Solution (Binary Search)

Intuition and Approach

We can do much better using binary search:

1. Binary Search on Divisor:
   The answer lies between 1 and the largest number in the array. Use binary search to find the smallest divisor.
2. Check If It Meets the Threshold:
   For each mid value (divisor), calculate the total sum. If it’s within the threshold, try a smaller divisor; otherwise, try a larger one.
3. Why does this work?
   The total sum function is monotonic: as the divisor increases, the sum decreases. Binary search is perfect for this.

Code Implementation

import math
from typing import List

class Solution:
    def calTotal(self, nums, n):
        total = 0
        for num in nums:
            total = total + math.ceil(num / n)  # Divide and round up for each element
        return total

    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        maxi = max(nums)
        low = 1
        high = maxi
        ans = 0
        while low <= high:
            mid = (low + high) // 2
            total = self.calTotal(nums, mid)
            if total <= threshold:
                ans = mid         # Try to find a smaller valid divisor
                high = mid - 1
            else:
                low = mid + 1     # Need a larger divisor
        return ans

Code Explanation

• Use binary search between 1 and the maximum number in the array.
• For each mid divisor, calculate the total sum.
• If the sum is within threshold, store the divisor and try smaller.
• If not, try larger divisors.
• Return the minimum valid divisor found.

Dry Run

Input:
nums = [1], threshold = 6

• low = 1, high = 9
• mid = 5, total = 5 (valid, try smaller → high = 4)
• mid = 2, total = 10 (too high, try larger → low = 3)
• mid = 3, total = 7 (too high, try larger → low = 4)
• mid = 4, total = 7 (too high, try larger → low = 5)
• Loop ends, answer is 5.

Time and Space Complexity

• Time Complexity: O(n * log(max(nums)))
  Binary search on divisor, checking all elements for each guess.
• Space Complexity: O(1)
  Only variables for counting.

Conclusion

The optimal solution is efficient and works well for large arrays and high values. It’s the best approach for interviews and practical use.

Final Thoughts

The “Find the Smallest Divisor Given a Threshold” problem is a great example of how to optimize from brute force to an efficient binary search solution. Start with brute force to understand the basics, then use binary search for best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.