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) =
4threshold (int) =
6Returns (int)
5Example 2
Input
nums (int[]) =
[44,22,33,11,1]size (int) =
5threshold (int) =
5Returns (int)
44Example 3
Input
nums (int[]) =
[2,3,5,7,11]size (int) =
5threshold (int) =
11Returns (int)
3The 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 leftReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run