# Find the Smallest Divisor Given a Threshold in Python

## Problem:

Given an array of integers `nums`

and an integer `threshold`

, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the **smallest** divisor such that the result mentioned above is less than or equal to `threshold`

.

Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).

It is guaranteed that there will be an answer.

## 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).
```

**Constraints:**

```
1 <= nums.length <= 5 * 10^4
1 <= nums[i] <= 10^6
nums.length <= threshold <= 10^6
```

## Explanation

- We need to find the smallest divisor such that the sum of nums is less than the threshold.
- The minimum value of the divisor can be 1 in that case sum of nums will remain the same whereas the maximum value of the divisor can be the maximum value in nums that will result in a minimum sum
- Basically, the value of the divisor will be in the range 1 to max(nums)
- Now we just need to check for every value in this range
- This problem can be solved by applying a binary search to get the optimal value of the divisor.

## Solution:

```
class Solution:
def smallestDivisor(self, nums: List[int], threshold: int) -> int:
def check(mid):
result = 0
for num in nums:
result += math.ceil(num / mid)
if result > threshold:
return False
return True
left = 1
right = max(nums)
while left <= right:
mid = (left + right) // 2
if check(mid):
right = mid - 1
else:
left = mid + 1
return left
```