Find the Smallest Divisor Given a Threshold

medium binary search

Problem

You get an array of positive integers nums and an integer threshold. Pick a positive integer divisor d, divide every element by it, and round each quotient up; the cost of d is the sum of those ceilings. Return the smallest d whose cost is at most threshold (the inputs guarantee such a divisor exists).

Inputnums = [1, 2, 5, 9], threshold = 6

Output5

With d = 5 the sum is ⌈1/5⌉+⌈2/5⌉+⌈5/5⌉+⌈9/5⌉ = 1+1+1+2 = 5 ≤ 6, but d = 4 already gives 1+1+2+3 = 7 > 6.

nums (comma-separated)

threshold

def smallest_divisor(nums, threshold):
    def ceil_sum(d):
        return sum((x + d - 1) // d for x in nums)

    lo, hi = 1, max(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if ceil_sum(mid) <= threshold:
            hi = mid          # mid works; try a smaller divisor
        else:
            lo = mid + 1      # sum too big; divisor must grow
    return lo

function smallestDivisor(nums, threshold) {
  const ceilSum = (d) => nums.reduce((s, x) => s + Math.ceil(x / d), 0);
  let lo = 1, hi = Math.max(...nums);
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (ceilSum(mid) <= threshold) hi = mid; // mid works; try smaller
    else lo = mid + 1;                       // sum too big; grow d
  }
  return lo;
}

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int lo = 1, hi = 0;
        for (int x : nums) hi = Math.max(hi, x);
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            int sum = 0;
            for (int x : nums) sum += (x + mid - 1) / mid;
            if (sum <= threshold) hi = mid;  // mid works; try smaller
            else lo = mid + 1;               // sum too big; grow d
        }
        return lo;
    }
}

int smallestDivisor(vector<int>& nums, int threshold) {
    int lo = 1, hi = *max_element(nums.begin(), nums.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        long long sum = 0;
        for (int x : nums) sum += (x + mid - 1) / mid;
        if (sum <= threshold) hi = mid;   // mid works; try smaller
        else lo = mid + 1;                // sum too big; grow d
    }
    return lo;
}

Explanation

The key insight is monotonicity: as the divisor d grows, every term ⌈x/d⌉ can only stay the same or shrink, so the total sum never increases. That means the predicate "sum ≤ threshold" looks like false, false, …, false, true, true, …, true over increasing d — and finding the first true in a monotone predicate is exactly what binary search on the answer does.

The search space is [1, max(nums)]. With d = 1 the sum equals the sum of all elements (the largest it can be), and with d = max(nums) every term is already 1, giving the smallest possible sum n. Since a valid answer is guaranteed, it must lie in this range — no point trying divisors beyond the maximum element.

We run the classic lo < hi boundary search. At each step we compute mid and its ceiling sum. If the sum fits within the threshold, mid is feasible, but a smaller divisor might also work, so we keep it in the window with hi = mid. If the sum is too big, mid (and everything below it) is hopeless, so lo = mid + 1. When the pointers meet, they sit on the smallest feasible divisor.

Walking the default example nums = [1, 2, 5, 9], threshold = 6: the window starts at [1, 9]. Trying mid = 5 gives 1+1+1+2 = 5 ≤ 6, so hi = 5. Trying mid = 3 gives 1+1+2+3 = 7 > 6, so lo = 4. Trying mid = 4 gives 1+1+2+3 = 7 > 6 again, so lo = 5. Now lo == hi == 5, and 5 is the answer.

Each feasibility check scans the array once, costing O(n), and binary search performs O(log max(nums)) checks, for O(n log max(nums)) total time. Only a few counters are kept, so the extra space is O(1).

Time: O(n log max(nums)) Space: O(1)