Find the Smallest Divisor Given a Threshold

Problem Choose a positive integer divisor d; the cost is Σ ceil(nums[i] / d). Return the smallest d whose cost is <= threshold.

Input / Output

• Input: int array nums, int threshold (guaranteed >= n so an answer exists).
• Output: smallest valid divisor.

Constraints

• n up to 5*10^4, values up to 10^6; O(n log max) expected.

Example

• nums = [1,2,5,9], threshold = 6 → 5 (cost 1+1+1+2 = 5 ≤ 6; d=4 gives 7).