Coding Interview PatternsFind the Smallest Divisor Given a Threshold
MediumModified Binary Search
Find the Smallest Divisor Given a Threshold
Explanation & Solution
Description
Given an array of integers nums and an integer threshold, find the smallest divisor such that the result of dividing all elements by the divisor (rounded up) and summing them 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 (i.e., Math.ceil).
Input:nums = [1, 2, 5, 9], threshold = 6
0
1
1
2
2
5
3
9
Output: 5
Explanation: With divisor 5: ceil(1/5) + ceil(2/5) + ceil(5/5) + ceil(9/5) = 1 + 1 + 1 + 2 = 5 ≤ 6.
Constraints
1 <= nums.length <= 5 * 10^41 <= nums[i] <= 10^6nums.length <= threshold <= 10^6
Approach
Modified Binary Search pattern
1. Define the Search Space
- Minimum divisor:
1— gives the largest possible sum. - Maximum divisor:
max(nums)— every ceil(num / divisor) becomes 1.
2. Binary Search on Divisor
- For candidate divisor
mid, compute the sum ofceil(num / mid)for all elements.
3. Check Against Threshold
- If sum
<= threshold, divisormidworks → try smaller:hi = mid. - Otherwise, divisor too small:
lo = mid + 1.
4. Return the Smallest Divisor
- When
lo === hi, return the answer.
🧠 Key Insight
- The sum function is monotonically decreasing as the divisor increases, making it perfect for binary search on the answer.
Time
O(n · log(max(nums))) — binary search with linear check.Space
O(1).Visualization
Input:
[1, 2, 5, 9], threshold = 6
—
Press ▶ or use ← → to step through
Pointer iPointer jProcessedDone
18 steps