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.
This approach uses binary search to efficiently find the smallest divisor. The possible divisors can range from 1 to the maximum number in the array. For each candidate divisor, divide each number in the array, take the ceiling of the division result, sum it up, and compare against the threshold.
Binary search helps minimize the number of trials by adjusting the divisor range based on whether the threshold condition is met or not for a given divisor.
The code uses binary search to find the smallest divisor. The loop continues until 'left' and 'right' converge. For each middle value, we compute the sum of divisions rounded up (utilizing integer arithmetic for efficiency), and adjust the search range based on whether this sum is more or less than the threshold.
Time Complexity: O(n * log(max(nums))) where n is the number of elements in nums. Space Complexity: O(1) as we use constant additional space.
This method involves a simple linear search from divisor = 1 upwards, incrementally checking each candidate as a divisor. This approach is less efficient compared to binary search but helps understand the problem in a straightforward manner. We calculate the total sum of the divisions for each divisor and stop when the sum is less or equal to the threshold. Ensuring progressively checking divisors until a valid one is found assures correctness.
This code initiates a loop to test each divisor starting from 1 upwards until it finds the smallest divisor satisfying the condition. The ceiling of division is calculated with the same integer math trick as before.
Time Complexity: Potentially O(n * max(nums)). Space Complexity: O(1).
Notice that for number v, if the sum of results of dividing each number in nums by v is less than or equal to threshold, then all values greater than v satisfy the condition. There is a monotonicity, so we can use binary search to find the smallest v that satisfies the condition.
We define the left boundary of the binary search l=1, r=max(nums). Each time we take mid=(l+r)/2, calculate the sum of the results of dividing each number in nums by mid s, if s is less than or equal to threshold, then it means that mid satisfies the condition, we will update r to mid, otherwise we will update l to mid+1.
Finally, return l.
The time complexity is O(n times log M), where n is the length of the array nums and M is the maximum value in the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Approach 1: Binary Search | Time Complexity: O(n * log(max(nums))) where n is the number of elements in nums. Space Complexity: O(1) as we use constant additional space. |
| Approach 2: Linear Scan with Improved Accuracy | Time Complexity: Potentially O(n * max(nums)). Space Complexity: O(1). |
| Binary Search | — |
| 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 |
BS-14. Find the Smallest Divisor Given a Threshold | Binary Search • take U forward • 194,887 views views
Watch 9 more video solutions →Practice Find the Smallest Divisor Given a Threshold with our built-in code editor and test cases.
Practice on FleetCode