Find the Smallest Divisor Given a Threshold
Medium · Binary Search · Array · Binary Search
Problem
You are given an integer array nums and an integer threshold. Choose a positive integer divisor d, divide every element by d rounding up (so 7 / 3 counts as 3 and 9 / 3 as 3), and add up the results.
Return the smallest divisor d whose sum is less than or equal to threshold. The input guarantees that such a divisor exists.
Examples
Input: nums = [3,8,14], threshold = 7 Output: 4
d = 4 gives 1 + 2 + 4 = 7, which meets the threshold, while d = 3 gives 1 + 3 + 5 = 9.
Input: nums = [10,10], threshold = 2 Output: 10
Only a divisor of 10 or more turns each value into 1.
Input: nums = [1,2,5,9], threshold = 6 Output: 5
d = 5 gives 1 + 1 + 1 + 2 = 5. d = 4 gives 1 + 1 + 2 + 3 = 7, one too many.
Constraints
- 1 <= len(nums) <= 5 · 10^4
- 1 <= nums[i] <= 10^6
- len(nums) <= threshold <= 10^6
Approaches
- Try every divisor from 1 up — time O(n · d*), space O(1)
Follow-up
The same shape solves a whole family: the slowest eating speed that finishes in time, the smallest ship that carries everything in D days, the fewest days until enough flowers bloom. Each asks for the smallest value whose cost, computed in one pass, fits a budget. Spot the monotonic yes/no test and binary search on it.
Related problems
Start free on Cariara · Coding problems · System design studio
