☕ DSA Java Articles

Topics › Binary Search › BS on Answers

Find the smallest divisor

Medium TUF ID 93 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array nums of positive integers and an integer threshold. Choose a positive integer divisor d, divide every element by d, round each quotient up to the nearest integer, and add the results. Return the smallest d for which that sum is less than or equal to threshold. The usual version of the problem guarantees that threshold ≥ n, so an answer always exists; our implementation returns -1 if it does not.

Constraints: 1 ≤ n ≤ 5 * 10^4, 1 ≤ nums[i] ≤ 10^6, n ≤ threshold ≤ 10^6.

Example 1

nums = [1, 2, 5, 9], threshold = 6
answer = 5          // ceil(1/5) + ceil(2/5) + ceil(5/5) + ceil(9/5) = 1 + 1 + 1 + 2 = 5 <= 6; with d = 4 the sum is 7

Example 2

nums = [44, 22, 33, 11, 1], threshold = 5
answer = 44         // threshold equals n, so every term must be exactly 1, which forces d >= max

If this looks like Koko eating bananas with different nouns, that is because it is: the piles are nums, the speed is d, and the hour limit is threshold.

The sum for a fixed divisor

static long sumWithDivisor(int[] nums, int d) {
    long sum = 0;
    for (int x : nums) sum += ((long) x + d - 1) / d;
    return sum;
}

(x + d - 1) / d is integer ceil(x / d) for positive operands. The accumulator is a long: with 5 * 10^4 elements of 10^6 and d = 1 the sum is 5 * 10^10, which overflows int. The cast on x also protects x + d - 1 when both are large.

Approach 1: Brute force, try every divisor

Intuition. Any d ≥ max(nums) makes every term ceil(x / d) = 1, so the sum is exactly n, the smallest it can ever be. Divisors above max therefore never help, and the candidates are 1, 2, ..., max. Larger divisors give smaller (or equal) sums, so scanning from 1 upwards and stopping at the first divisor that satisfies the threshold yields the minimum.

Algorithm.

  1. Compute max = max(nums).
  2. For d = 1, 2, ..., max: if sumWithDivisor(nums, d) ≤ threshold, return d.
  3. Return -1 (only when threshold < n).
static int bruteForce(int[] nums, int threshold) {
    int max = 0;
    for (int x : nums) max = Math.max(max, x);
    for (int d = 1; d <= max; d++) {
        if (sumWithDivisor(nums, d) <= threshold) return d;
    }
    return -1;
}

Complexity. Time O(n * max): up to 10^6 divisors, each needing an O(n) pass, around 5 * 10^10 operations in the worst case. Space O(1).

Approach 2: Optimal, binary search on the divisor

Intuition. Let ok(d) be “the rounded-up sum for divisor d is at most threshold”. Increasing d can only decrease each ceil(x / d), so the sum is non-increasing in d, and ok is monotonic: false for small divisors, true from some point on. The answer is the first true value. Binary search over [1, max]: when ok(mid) holds, record mid and try smaller divisors; otherwise try larger ones.

Algorithm.

  1. Compute max = max(nums); set lo = 1, hi = max, ans = -1.
  2. While lo ≤ hi:
    • mid = lo + (hi - lo) / 2.
    • If sumWithDivisor(nums, mid) ≤ threshold: ans = mid, hi = mid - 1.
    • Else: lo = mid + 1.
  3. Return ans.
static int optimal(int[] nums, int threshold) {
    int max = 0;
    for (int x : nums) max = Math.max(max, x);
    int lo = 1, hi = max, ans = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (sumWithDivisor(nums, mid) <= threshold) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    return ans;
}

Dry run on nums = [1, 2, 5, 9], threshold = 6:

lo hi mid terms sum ≤ 6? ans next
1 9 5 1, 1, 1, 2 5 yes 5 [1, 4]
1 4 2 1, 1, 3, 5 10 no 5 [3, 4]
3 4 3 1, 1, 2, 3 7 no 5 [4, 4]
4 4 4 1, 1, 2, 3 7 no 5 [5, 4] stop

Result 5.

Complexity. Time O(n log max): about 20 iterations for max = 10^6, each an O(n) scan, so roughly 10^6 operations. Space O(1).

Here ans starts at -1 rather than at max, because the problem as implemented does not assume threshold ≥ n. When the guarantee holds, ok(max) is true and the search always records a value; when it does not, no divisor works and -1 is the honest answer.

Why the monotonic argument is airtight

It is tempting to wave hands at “bigger divisor, smaller sum”, so here is the precise statement. For positive integers x and d < d', x / d' < x / d as real numbers, hence ceil(x / d') ≤ ceil(x / d). Summing over all elements gives sum(d') ≤ sum(d). Therefore if sum(d) ≤ threshold then sum(d') ≤ threshold too: feasibility of d implies feasibility of every larger divisor, which is exactly the F...F T...T shape binary search needs. Note the inequality on each term is not strict (ceil(5/4) = ceil(5/5) = 1), which is why the sum can stay flat for a while, as rows three and four of the dry run show. Flat stretches are fine; the search only needs “never increases”.

Edge cases and pitfalls