Smallest Divisor Given a Threshold, thesarfo

Find the smallest divisor such that dividing every array element by it (rounding each division up) sums to at most threshold. (LeetCode 1283)

For [1,2,5,9], threshold 6: divisor 4 gives ceil(1/4)+ceil(2/4)+ceil(5/4)+ceil(9/4) = 7 (too big); divisor 5 gives 5 (fits).

Search space: [1, max(nums)] — larger divisors always produce smaller-or-equal sums, so the feasible divisors form a contiguous suffix of that range.

public int smallestDivisor(int[] nums, int threshold) {
    int max = 0;
    for (int num : nums) {
        max = Math.max(max, num);
    }

    int low = 1, high = max;
    int answer = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        int sum = sumDivisors(nums, mid);

        if (sum > threshold) {
            low = mid + 1; // need a larger divisor to shrink the sum
        } else {
            answer = mid;
            high = mid - 1; // try a smaller divisor
        }
    }

    return answer;
}

public int sumDivisors(int[] nums, int divisor) {
    int sum = 0;
    for (int num : nums) {
        sum += Math.ceil((double) num / divisor);
    }
    return sum;
}

Time: O(n × log(max)).