Watch 10 video solutions for Find the Smallest Divisor Given a Threshold, a medium level problem involving Array, Binary Search. This walkthrough by take U forward has 194,887 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 * 1041 <= nums[i] <= 106nums.length <= threshold <= 106Problem Overview: You are given an integer array nums and a threshold. Choose a divisor such that every number in the array is divided by it, rounded up using ceil(num / divisor). The goal is to return the smallest divisor where the total sum of these rounded results does not exceed the threshold.
Approach 1: Linear Scan with Improved Accuracy (Time: O(n * m), Space: O(1))
The most direct strategy checks every possible divisor from 1 up to max(nums). For each candidate divisor, iterate through the array and compute ceil(num / divisor). Accumulate the values and stop early if the sum exceeds the threshold. The first divisor that keeps the sum within the threshold is the answer. This approach is simple and useful for understanding the constraint behavior, but it becomes slow when the maximum value in nums is large because every divisor candidate must be evaluated.
Approach 2: Binary Search on the Divisor (Time: O(n log m), Space: O(1))
The key observation: as the divisor increases, the total sum of ceil(num / divisor) monotonically decreases. Larger divisors produce smaller division results. This monotonic property allows you to apply binary search over the range [1, max(nums)]. For a mid divisor, iterate through the array and compute the total rounded division sum. If the sum is greater than the threshold, the divisor is too small, so move the search to the right. Otherwise, try smaller divisors on the left to minimize the answer. Each check costs O(n), and the search range halves every step, leading to O(n log m) time where m = max(nums).
Recommended for interviews: Binary search on the answer space is the expected solution. Interviewers look for the recognition that the result function is monotonic with respect to the divisor. A quick brute-force explanation shows you understand the problem, but implementing the O(n log m) binary search demonstrates algorithmic maturity and familiarity with search-space optimization patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan with Improved Accuracy | O(n * m) | O(1) | Good for understanding the brute-force behavior or when max(nums) is very small |
| Binary Search on Divisor | O(n log m) | O(1) | Best general solution when the divisor range is large and performance matters |