Smallest Divisor Given a Threshold

Share

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.

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

Solution Approach

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.
Java
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)