Finding the Minimum Divisor to Keep the Sum Below a Threshold

The objective is to determine the smallest positive integer divisor such that the sum of the divisions of an integer array does not exceed a given threshold. Each division operation must be rounded up to the nearest integer. Given the constraints, a linear search is inefficient, making binary search the optimal approach for locating the minimum divisor.

First, define the search range. The minimum possible divisor is 1, and the maximum possible divisor is the largest value in the array, as dividing by the maximum element will minimize the sum. Next, iterate using binary search. For each midpoint divisor, calculate the total sum by dividing each element and rounding up.

Compare the calculated sum with the threshold. If the sum is less than or equal to the threshold, it means the divisor is a candidate, and we should try to find a smaller one by adjusting the upper bound. If the sum exceeds the threshold, the divisor is too small, and we need to increase the lower bound. This process continues until the search space is exhausted, at which point the smallest valid divisor is identified.

Below is a clean implementation of this logic:

/**
 * @param {number[]} nums
 * @param {number} threshold
 * @return {number}
 */
var smallestDivisor = function(nums, threshold) {
    let left = 1;
    let right = Math.max(...nums);
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        let total = 0;
        
        for (const val of nums) {
            total += Math.ceil(val / mid);
        }
        
        if (total <= threshold) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};

Tags: Binary Search algorithm javascript LeetCode

Posted on Sat, 26 Sep 2026 16:53:07 +0000 by scott56hannah