Smallest Divisor Given Threshold
mediumTime: O(n log max)Space: O(1)
Signals to notice
smallest divisor keeping sum ≤ thresholdbinary search on divisorceiling division
Brute force first
Try every divisor from 1 to max(nums) — O(max × n).
The key insight
Binary search on divisor in [1, max(nums)]. For each candidate, compute sum of ceil(nums[i]/divisor). If sum ≤ threshold, divisor works (try smaller). O(n log max).
What must stay true
Larger divisor → smaller sum (monotonic). Binary search finds the smallest divisor where sum ≤ threshold.
Easy way to go wrong
Using floor division instead of ceiling — each element contributes ceil(num/d), not floor.