Find the smallest positive integer divisor such that the sum of the ceiling divisions of the array elements by that divisor does not exceed a threshold.
Smallest Divisor Given a Threshold
gfgProblem
Given an array of positive integers nums and a positive integer threshold, choose a positive integer divisor d.
For each number nums[i], compute ceil(nums[i] / d) and add all these values together. Your task is to return the smallest divisor d such that the total sum is less than or equal to threshold.
Because the answer can be large, search efficiently rather than trying every divisor one by one.
Goal
Find the minimum d > 0 satisfying:
Input Format
nums: an array of positive integersthreshold: a positive integer
You may assume the answer exists for the given input.
Output Format
Return the smallest positive integer divisor that makes the sum of ceiling divisions at most threshold.
Constraints
1 <= nums.lengthnums[i] > 0threshold > 0- The answer is a positive integer
- Use an efficient approach; a linear scan over all divisors may be too slow for large values
Example 1
Input
nums = [1,2,5,9], threshold = 6
Output
5
Explanation
For d = 5, the sum is ceil(1/5) + ceil(2/5) + ceil(5/5) + ceil(9/5) = 1 + 1 + 1 + 2 = 5, which is within the threshold. Using d = 4 gives 1 + 1 + 2 + 3 = 7, which is too large. So the smallest valid divisor is 5.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.