Binary Search - Smallest Divisor Given a Threshold

Given an array nums and an integer threshold, find the smallest positive integer divisor such that the sum of ceil(nums[i]/divisor) for all i is <= threshold.

Input: nums=[1,2,5,9], threshold=6 → Output: 5

Input: nums=[44,22,33,11,1], threshold=5 → Output: 44

Binary search on divisor d in [1, max(nums)]. For each d, compute sum of ceil values. If sum <= threshold, try smaller d.

lo=1, hi=max(nums).
For mid, compute sum = sum(ceil(n/mid)) for each n.
If sum <= threshold: hi=mid (try smaller).
Else: lo=mid+1.

class Solution { public int smallestDivisor(int[] nums, int threshold) { int lo = 1, hi = 0; for (int n : nums) hi = Math.max(hi, n); while (lo < hi) { int mid = lo + (hi - lo) / 2; long sum = 0; for (int n : nums) sum += (n + mid - 1) / mid; if (sum <= threshold) hi = mid; else lo = mid + 1; } return lo; } }

Time Complexity: O(N log M) where M=max(nums)
Space Complexity: O(1)