#1283
Find the Smallest Divisor Given a Threshold
Medium Binary search on the answer
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Pick a positive divisor, divide every number by it rounding up, and sum the results. Return the smallest divisor whose sum is at most threshold.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the smallest divisor so that the sum of rounded-up divisions stays within the threshold.
Why this works: a bigger divisor makes the sum smaller or equal, so binary search the divisor.
Example: [1, 2, 5, 9], threshold 6
d=5: 1+1+1+2 = 5 ✓d=4: 1+1+2+3 = 7 ✗ → answer 5
✦Hints open one at a time
A bigger divisor never makes the sum bigger.
Search the divisor between 1 and the maximum element.
↗Approach
Binary search the first divisor d with sum(ceil(x / d)) <= threshold.
</>Solution (Java)
class Solution {
public int smallestDivisor(int[] nums, int threshold) {
int lo = 1, hi = 0;
for (int x : nums) hi = Math.max(hi, x);
while (lo < hi) {
int d = (lo + hi) >>> 1;
long sum = 0;
for (int x : nums) sum += (x + d - 1) / d;
if (sum <= threshold) hi = d;
else lo = d + 1;
}
return lo;
}
}!Common mistake
Using normal integer division instead of rounding up: use (x + d − 1) / d.
Complexity
- Time: O(n log M).
- Space: O(1).
Topic: Binary Search
🎬 Episodes 21–23: video coming soon