Find the Smallest Divisor Given a Threshold

Problem Statement

Given nums and a threshold, find the smallest positive divisor such that the sum of ceil(num / divisor) over all numbers is <= threshold.

Example

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

Approach

As the divisor grows, the summed quotient shrinks — a monotone predicate, so binary-search the divisor in [1, max(nums)]. For each candidate, compute the ceiling-division sum and move toward the smallest divisor that stays within the threshold.

Complexity

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

Solution Code

Python

import math
def smallestDivisor(nums, threshold):
    lo, hi = 1, max(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        total = sum(math.ceil(n / mid) for n in nums)
        if total <= threshold:
            hi = mid
        else:
            lo = mid + 1
    return lo

Java

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;
        int total = 0;
        for (int n : nums) total += (n + mid - 1) / mid;
        if (total <= threshold) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

C++

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;
        int total = 0;
        for (int n : nums) total += (n + mid - 1) / mid;
        if (total <= threshold) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Key Takeaways

• Larger divisor -> smaller sum: the monotonicity that enables binary search.
• Ceiling division in integers: (n + d - 1) / d.
• Reference: LeetCode 1283 (Find the Smallest Divisor Given a Threshold).