Find The Smallest Divisor Given A Threshold - Leetcode Solution

Problem Statement: Given an array of integers nums and an integer threshold, we will choose a positive integer divisor, divide all the array by it, and sum the division's result. Find the smallest divisor such that the result mentioned above is less than or equal to the threshold.

Each resulted sum must be rounded up to the nearest integer greater than or equal to that element. For example, consider the array [1, 2, 3, 4, 5, 6, 7, 8, 9] and the divisor is 2. The returned result will be 21, which is the sum of [1, 1, 2, 2, 3, 3, 4, 4, 5]. Notice that the sum is rounded up.

Example: Input: nums = [1,2,5,9], threshold = 6 Output: 5 Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).

Solution: To solve this problem, we can implement a binary search in a range between 1 and max(nums). The problem states that we must choose a positive integer divisor; therefore, each time we check the divisor, we can apply it to the array. If the result of the division is greater than the threshold, we increase the lower bound of the search range by one; otherwise, we decrease the upper bound of the search range by one.

Let's write the code now:

def smallestDivisor(nums, threshold):
    left = 1
    right = max(nums)
    while left <= right:
        divisor = (left + right) // 2
        s = sum((i + divisor - 1) // divisor for i in nums)
        if s > threshold:
            left = divisor + 1
        else:
            right = divisor - 1
    return left

The time complexity of this solution is O(n*log(max(nums))), where n is the size of the input array, which will iterate over every value, and binary search will perform log(max(nums)) operations.

1