Find the Smallest Divisor Given a Threshold

Problem

Given an integer array and a threshold, return the smallest positive divisor d such that the sum of ceil(nums[i] / d) over all i is ≤ threshold.

Constraints

• 1 ≤ nums.length ≤ 5·10⁴
• 1 ≤ nums[i] ≤ 10⁶
• nums.length ≤ threshold ≤ 10⁶

Approach — Binary Search

This is a Binary Search problem. The idea: repeatedly halve the search space, discarding the half that can't contain the answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(log n) time.

Solution code

Python

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

Java

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int lo = 1, hi = 1;
        for (int x : nums) hi = Math.max(hi, x);
        while (lo < hi) {
            int m = lo + (hi - lo) / 2;
            long sum = 0;
            for (int x : nums) sum += (x + m - 1) / m;
            if (sum <= threshold) hi = m;
            else                   lo = m + 1;
        }
        return lo;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.