Find the Smallest Divisor Given a Threshold

Master this topic with zero to advance depth.

Find the Smallest Divisor Given a Threshold

Given an array nums and an integer threshold, find the smallest divisor $d$ such that the sum of the division results (rounded up) is $\\le$ threshold.

Medium

Examples

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

Approach 1

Level I: Brute Force

Intuition

Try every divisor $d$ from 1 up to $\\max(nums)$ and check the sum condition.

⏱ $O(MaxValue \\cdot N)$💾 $O(1)$

Detailed Dry Run

nums=[1,2,5,9], threshold=6.

d=4: ceil(1/4)+ceil(2/4)+ceil(5/4)+ceil(9/4) = 1+1+2+3 = 7 > 6.
d=5: ceil(1/5)+ceil(2/5)+ceil(5/5)+ceil(9/5) = 1+1+1+2 = 5 <= 6. Return 5.

java

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int maxVal = 0; for (int n : nums) maxVal = Math.max(maxVal, n);
        for (int d = 1; d <= maxVal; d++) {
            int sum = 0;
            for (int n : nums) sum += (n + d - 1) / d;
            if (sum <= threshold) return d;
        }
        return maxVal;
    }
}

Approach 2

Level II: Optimal (Mathematical Bound Optimization)

Intuition

Instead of starting the brute force from $d=1$ , we can observe that $d$ must be at least $\\lceil \\frac{\\sum nums}{\\text{threshold}} \\rceil$ . This provides a tighter lower bound for our search.

⏱ $O((MaxValue - LowerBound) \\cdot N)$💾 $O(1)$

Detailed Dry Run

nums=[1,2,5,9], threshold=6. Sum=17. Lower bound $d = \\lceil 17/6 \\rceil = 3$ .

d=3: sum = 7 > 6.
d=4: sum = 7 > 6.
d=5: sum = 5 <= 6. Return 5.

java

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        long sumAll = 0; for (int n : nums) sumAll += n;
        int start = (int)Math.ceil((double)sumAll / threshold);
        for (int d = start; ; d++) {
            int sum = 0;
            for (int n : nums) sum += (n + d - 1) / d;
            if (sum <= threshold) return d;
        }
    }
}

Approach 3

Level III: Optimal (Binary Search on Answer)

Intuition

The sum of division results is a non-increasing function of the divisor $d$ . Binary search in the range $[1, \\max(nums)]$ .

⏱ $O(N \\log(MaxValue))$💾 $O(1)$

Detailed Dry Run

nums=[1,2,5,9], threshold=6. [1, 9].

Mid 5: sum = 5 <= 6. R=5.
Mid 2: sum = 1+1+3+5 = 10 > 6. L=3.
Mid 3: sum = 1+1+2+3 = 7 > 6. L=4.
Mid 4: sum = 1+1+2+3 = 7 > 6. L=5. Result 5.

java

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int l = 1, r = 1000000;
        for (int n : nums) r = Math.max(r, n);
        while (l < r) {
            int mid = l + (r - l) / 2, sum = 0;
            for (int n : nums) sum += (n + mid - 1) / mid;
            if (sum <= threshold) r = mid; else l = mid + 1;
        }
        return l;
    }
}

← Previous QuestionMinimum Number of Days to Make m Bouquets

Next Question →Koko Eating Bananas

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.