Array Sorting Binary Search
Intermediate Level

Implement the smallestDivisorUnderThreshold method that finds the smallest divisor satisfying a threshold condition.

You are given an array of positive integers and a threshold. Choose a positive divisor. For each number, divide it by the divisor and round up to the nearest integer.

Return the smallest divisor such that the sum of all rounded-up results is less than or equal to the threshold.

Example 1
Input:
nums (int[]) = [1,2,5,9]
size (int) = 4
threshold (int) = 6
Return:
(int) 5
Example 2
Input:
nums (int[]) = [44,22,33,11,1]
size (int) = 5
threshold (int) = 5
Return:
(int) 44
Example 3
Input:
nums (int[]) = [2,3,5,7,11]
size (int) = 5
threshold (int) = 11
Return:
(int) 3

The answer can be found using binary search.

If a divisor is too small, the rounded sum becomes too large. If a divisor works, any larger divisor will also work. This monotonic behavior allows binary search between 1 and the maximum value in the array.

For each candidate divisor, compute the rounded sum and move the search range accordingly.

Pseudocode:

function smallestDivisorUnderThreshold(nums, size, threshold):
    left = 1
    right = maximum value in nums
    while left < right:
        mid = (left + right) / 2
        total = 0
        for each number in nums:
            total += ceiling(number / mid)
        if total <= threshold:
            right = mid
        else:
            left = mid + 1
    return left
Run your code to see the result.