Course4all

Find the Smallest Divisor Given a Threshold

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Binary Search.

Find the Smallest Divisor Given a Threshold

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

Examples

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

Level I: Brute Force

Intuition

Try every divisor dd from 1 up to max(nums)\\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=1d=1, we can observe that dd must be at least lceilfracsumnumstextthresholdrceil\\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=lceil17/6rceil=3d = \\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 dd. Binary search in the range [1,max(nums)][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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionMinimum Number of Days to Make m Bouquets
Next Question →Koko Eating Bananas