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 ceil(1/5)+ceil(2/5)+ceil(5/5)+ceil(9/5) = 1+1+1+2 = 5 ≤ 6; d=4 gives 7).

Expected approach

• Cost is non-increasing in d → binary search d in [1, max(nums)]: compute cost(mid) in O(n) (integer ceil: (x + d − 1) / d); cost <= threshold → try smaller (hi = mid), else lo = mid + 1. O(n log max). Same monotone-predicate family as Koko Eating Bananas / Ship Packages — name the pattern and get the ceil arithmetic right.