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 1:
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). 

Example 2:
Input: nums = [2,3,5,7,11], threshold = 11
Output: 3

Example 3:
Input: nums = [19], threshold = 5
Output: 4

 
Constraints:

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

Difficulty: interview

Starter code:

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        

Solutions:
import numpy as np
import math

class Solution:
    
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        if len(nums) == 1:
            return int(math.ceil(nums[0]/threshold))
        
        np_nums = np.array(nums) 
        low, high = 1, np.max(np_nums)
        
        divisors = []
        while low + 1 < high:
            mid = (low + high) // 2
            
            if np.sum(np.ceil(np_nums/mid)) > threshold:
                low = mid
            else:
                high = mid
            
        if np.sum(np.ceil(np_nums/low)) <= threshold:
            return low
        
        return high


from numpy import array, ceil, sum
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        nums = array(nums)
        l, r = ceil(sum(nums)/threshold), max(nums)
        
        while l < r:
            mid = (l+r)//2
            if sum(ceil(nums/mid)) <= threshold:
                r = mid
            else:
                l = mid + 1
        
        return int(r)

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def helper(nums, ans):
            return sum([ (i + ans - 1) // ans for i in nums])
        
        l =  1
        r = max(nums)
        while l < r:
            mid  = l + (r - l) // 2
            sumv = helper(nums, mid)
            if sumv <= threshold:
                r = mid 
            else:
                l = mid + 1
            
        return l


import math
class Solution:
    def calculateSum(self, nums, divisor):
        Sum = 0
        for num in nums:
            Sum += math.ceil(num / divisor)
        return Sum
    
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        maxValue = max(nums)
        
        l = 1
        r = maxValue
        
        while l <= r:
            mid = (l + r) // 2
            # print(mid)
            if mid == maxValue:
                return maxValue
                
            sum1 = self.calculateSum(nums, mid)
            sum2 = self.calculateSum(nums, mid + 1)
            # print(sum1, sum2)
            if sum2 <= threshold and sum1 > threshold:
                return mid + 1
            
            if sum1 <= threshold:
                r = mid - 1
            
            if sum1 > threshold:
                l = mid + 1
        return 1

class Solution:
    def divide(self, num, divisor):
        return -((-num)//divisor)
    
    def getQuotient(self, nums, divisor):
        output = 0
        for num in nums:
            output += ceil(num/divisor)
        return output
    
    def getResult(self, results, divisor, nums):
        #if divisor in results:
        #    return results[divisor]
        #else:
        #    results[divisor] = self.getQuotient(nums, divisor)
        #    return results[divisor]
        return self.getQuotient(nums, divisor)
    def helper(self, results, nums, i, j, threshold):
        if i == j:
            return i
        
        mid = (i+j)//2
        if mid == 1:
            return mid
        elif self.getResult(results, mid, nums) <= threshold and self.getResult(results, mid-1, nums) > threshold:
            return mid
        elif self.getResult(results, mid, nums) <= threshold:
            return self.helper(results, nums, i, mid-1, threshold)
        else:
            return self.helper(results, nums, mid+1, j, threshold)
    

    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        maxDivisor = ceil(2*sum(nums)/threshold)
        #print(maxDivisor)
        #maxDivisor = 1000000
        results = dict()
        
        return self.helper(results, nums, 1, maxDivisor, threshold)


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        lo, hi= 1, max(nums)
        while lo <= hi:
            mid = (lo + hi) // 2
            if sum([math.ceil(i/mid) for i in nums]) <= threshold:
                hi = mid - 1
            else:
                lo = mid + 1
        return lo

import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:

#         left, right = 1, max(nums)
#         while left + 1 < right:
#             mid = (left + right) // 2
#             div_sum =  self.get_sum(mid, nums)
#             if div_sum > threshold:
#                 left = mid
#             else:
#                 right = mid
        
#         div_sum = self.get_sum(left, nums)
#         if div_sum <= threshold:
#             return left
#         return right
        
    
#     def get_sum(self, divisor, nums):
#         res = 0
#         for n in nums:
#             tmp = n // divisor
#             if tmp * divisor < n:
#                 tmp += 1
            
#             res += tmp
        
#         return res
    
        dicti = {0:False}
        def chk(nmb):
            if nmb in dicti:
                return dicti[nmb]
            val = 0
            for num in nums:
                val += math.ceil(num/nmb)
                if val > threshold:
                    dicti[nmb] = False
                    return False
            dicti[nmb] = True
            return dicti[nmb]
            
        high = sum(nums)
        low = math.ceil(high/threshold)  
        while low <= high:
            mid = (low + high)//2
            
            if chk(mid):
                high = mid - 1
            elif not chk(mid):
                low = mid + 1
        return low-1 if chk(low-1) else high+1
                


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        l, r = 1, max(nums)
        while l < r:
            m = (l + r) // 2
            sum_num = 0
            for i in nums:
                sum_num += (i + m - 1) // m
            if sum_num > threshold:
                l = m + 1
            else:
                r = m
        return l

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        # if the sum <= threshold, the divisor is big enough
        
        low, high = 1, max(nums)
        
        while low < high:
            mid = (low + high) // 2
        
            # if the sum > threshold, the divisor is too small
            if sum((i + mid - 1) // mid for i in nums) > threshold:
                low = mid + 1
            else:
                high = mid
                
        return low


class Solution:
    def divide(self, num, divisor):
        return -((-num)//divisor)
    
    def getQuotient(self, nums, divisor):
        output = 0
        for num in nums:
            output += ceil(num/divisor)
        return output
    
    def getResult(self, results, divisor, nums):
        #if divisor in results:
        #    return results[divisor]
        #else:
        #    results[divisor] = self.getQuotient(nums, divisor)
        #    return results[divisor]
        return self.getQuotient(nums, divisor)
    def helper(self, results, nums, i, j, threshold):
        if i == j:
            return i
        
        mid = (i+j)//2
        if mid == 1:
            return mid
        elif self.getResult(results, mid, nums) <= threshold and self.getResult(results, mid-1, nums) > threshold:
            return mid
        elif self.getResult(results, mid, nums) <= threshold:
            return self.helper(results, nums, i, mid-1, threshold)
        else:
            return self.helper(results, nums, mid+1, j, threshold)
    

    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        maxDivisor = self.divide(2*sum(nums), threshold)
        #print(maxDivisor)
        #maxDivisor = 1000000
        results = dict()
        
        return self.helper(results, nums, 1, maxDivisor, threshold)


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        # (s + n) / x <= threshold
        # x >= (s + n) / threshold
        # x >= (s + n) // threshold
        
        # n <= t
        # n >= 1
        # t >= 1
        # s / x <= t
        # x <= s
        
        n, j = len(nums), sum(nums)
        i = (j + n) // threshold
        i = 1 if i == 0 else i
        while i < j-1:
            k = (i + j) // 2
            ss = sum([math.ceil(n / k) for n in nums])
            if ss > threshold:
                i = k
            else:
                j = k

        if sum([math.ceil(n / i) for n in nums]) <= threshold:
            return i
        else:
            return j


import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        self.nums = nums
        self.threshold = threshold
        num_sum = sum(nums)
        l = math.floor(num_sum / threshold)-1
        h = num_sum
        m = math.ceil((l+h) / 2)
        while h != m:
#            print(l,h)
            if self.validate_divisor(m):
                h = m
            else:
                l = m
            m = math.ceil((l+h) / 2)
        return h
        
    def validate_divisor(self, divisor):
        if divisor <= 0:
            return False
        s = sum(math.ceil(x / divisor) for x in self.nums)
#        print('validate', divisor, s, s <= self.threshold)
        return s <= self.threshold

import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def condition(divisor):
            return sum((num - 1) // divisor +1 for num in nums) <= threshold
        left, right = ceil(sum(nums)/threshold), max(nums)
        while left < right:
            mid = left + (right -left) //2
            if condition(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        l = 1; r = 2**31-1
        calc = lambda cand: sum(ceil(x/cand) for x in nums)
        while l + 1 < r:
            mid = l+(r-l)//2
            if  calc(mid) > threshold:
                l = mid
            else:
                r = mid
        if calc(l) <= threshold: return l
        else: return r
        
            


import math 
class Solution: 
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        # bruteforce 
        '''
        divisor = 0 
        trial_sum = float(inf) 
        while trial_sum > threshold:
            divisor += 1 
            trial_sum = 0 
            for num in nums: 
                trial_sum += math.ceil(num / divisor)
           

        return divisor 
        '''
        
        # binary search 
        low = 1 
        high = 100000000
        while (low <= high):
            mid = low + (high - low) // 2 
            if self.getSum(nums, mid) <= threshold: 
                high = mid - 1 
            elif self.getSum(nums, mid) > threshold: 
                low = mid + 1 
        return low
    def getSum(self, nums, divisor):
        trial_sum = 0 
        for num in nums: 
            trial_sum += math.ceil(num / divisor)
        return trial_sum 
    
    
            
    
            
        


import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def candidate(val):
            res = sum(math.ceil(v/val) for v in nums)
            return res <= threshold
        
        lo, hi = 1, max(nums)
        while lo < hi:
            med = lo + (hi-lo)//2
            if candidate(med):
                hi = med
            else:
                lo = med+1
        return hi

import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def posb(m):
            s=0
            for i in range(len(nums)):
                s+=math.ceil(nums[i]/m)
            return s>threshold
        l=1
        r=10**9
        while l<r:
            mid=(l+r)//2
            if posb(mid)==False:
                r=mid
            else:
                l=mid+1
        return l


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        def calculate(divisor):
            _sum=0
            for val in nums:
                _sum+=val//divisor + int(val%divisor!=0)
            return _sum
        
        
        start,end=1,sum(nums)
        while start<end:
            mid=start+(end-start)//2
            _sum=calculate(mid)
            if _sum>threshold:
                start=mid+1
            else:
                end=mid
        return start
            


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        #print(math.ceil(7/3))
        high = sum(nums)
        if high <= threshold: return 1
        
        def sum_divide(divisor):
            su = 0
            for num in nums:
                su += math.ceil(num / divisor)
                if su > threshold:
                    return False
            return True    
        
        low = 1
        while low < high:
            mid = low + (high - low) // 2
            if sum_divide(mid):
                high = mid
            else:
                low = mid + 1
                
        return low       


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        lo, hi = 1, max(nums)
        
        while lo <= hi:
            mid = (lo+hi)//2
            divisor_sum = sum([math.ceil(x/mid) for x in nums]) # will be larger
            next_sum = sum([math.ceil(x/(mid+1)) for x in nums]) # will be smaller
            
            if  next_sum <= threshold < divisor_sum:
                return mid+1
            elif next_sum > threshold:
                lo = mid + 1
            elif divisor_sum <= threshold:
                hi = mid - 1
        
        return 1

import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        # sum/divisor<= threshold
        # divisor >= sum/threshold
        def is_le(divisor):
            count = 0
            for num in nums:
                count += math.ceil(num/divisor)
                if count>threshold:
                    return False
            return True
        
        low = max(1,math.floor(sum(nums)/threshold))
        high = max(nums)
        while low<high:
            mid = low + (high-low)//2
            if is_le(mid):
                high = mid
            else:
                low = mid + 1
        return low


from math import ceil
def is_fine(nums,val,threshold):
    tot = 0
    for i in nums:
        tot += ceil(i/val)
    if tot <= threshold:
        return True
    else:
        return False
def bSearch(l,r,nums,threshold):
    if l <= r:
        mid = (l+r)//2
        high_val = is_fine(nums,mid,threshold)
        low_val = is_fine(nums,mid-1,threshold)
        if high_val is True and low_val is False:
            return mid
        elif high_val is False and low_val is False:
            return bSearch(mid+1,r,nums,threshold)
        else:
            return bSearch(l,mid-1,nums,threshold)
    else:
        return None
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        if sum(nums) <= threshold:
            return 1
        return bSearch(2,10**7,nums,threshold)
        


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        lo, hi = 1, max(nums)

        while lo < hi:
            mid = (lo+hi)//2                        
            print(sum([math.ceil(n/mid) for n in nums]))
            if sum([math.ceil(n/mid) for n in nums]) <= threshold:
                hi = mid
            else:
                lo = mid+1

        return lo

class Solution:
    def satisfyThreshold(self, nums, threshold, divisor):
        return sum((((n-1) // divisor) + 1 for n in nums)) <= threshold
        
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        left = 1
        right = max(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            if self.satisfyThreshold(nums, threshold, mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        val=sum(nums)
        n=len(nums)
        
        if val<=threshold:
            return 1
        
        p=val//threshold+int(val%threshold!=0)
        q=val//(max(1,threshold-n-1))
        q=q+4
        p=max(2,p)
        
        check=1
        
        while (p<q):
            mid=(p+q)//2
            count1=0
            count2=0
            for i in nums:
                count1=count1+(i//mid+int(i%mid!=0))
                count2=count2+(i//(mid-1)+int(i%(mid-1)!=0))
            if count1<=threshold and count2>threshold:
                return mid
            elif count1<=threshold and count2<=threshold:
                q=mid
            elif count1>threshold:
                p=mid+1
                
        
        
        


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        left = 1
        right = max(nums)
        while left <= right:
            mid = (right + left) // 2
            acc = 0
            for n in nums:
                acc += math.ceil(n/mid)
            # print(left, mid, right, '|', acc)
            if acc > threshold: left = mid + 1
            elif acc <= threshold: right = mid - 1
        return left


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def check(nums, a, th):
            for n in nums:
                th-=math.ceil(n/a)
                if th<0:
                    return False
            return True
        l,r=1,max(nums)
        while l<r:
            mid=(l+r)//2
            if check(nums, mid, threshold):
                r=mid
            else:
                l=mid+1
        return l

import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        nums.sort()
        return self.binSearch(1, nums[-1], nums, threshold)
    
    def binSearch(self, head, tail, nums, threshold):
        if head == tail:
            return head
        mid = (tail - head) // 2 + head
        ct = 0
        flag = True
        for num in nums:
            ct += math.ceil(num/mid)
            if ct > threshold:
                flag = False
                break
        if not flag: return self.binSearch(mid + 1, tail, nums, threshold)
        else: return self.binSearch(head, mid, nums, threshold)


#import math
from numpy import ceil
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def candidate(val):
            #res = sum(math.ceil(v/val) for v in nums)
            res = sum((v-1)//val + 1 for v in nums)
            return res <= threshold
        
        lo, hi = 1, max(nums)
        while lo < hi:
            med = lo + (hi-lo)//2
            if candidate(med):
                hi = med
            else:
                lo = med+1
        return hi

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        def thres(div):
            return sum([ceil(val/div) for val in nums])
        
        l,h=1,max(nums)
        
        while(l<=h):
            mid=l+((h-l)>>1)
            if thres(mid)<=threshold: h=mid-1
            else: l=mid+1
        
        return l


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        left = 1
        right = max(nums)
        while left < right:
            mid = (right + left) // 2
            acc = 0
            for n in nums:
                acc += math.ceil(n/mid)
            # print(left, mid, right, '|', acc)
            if acc > threshold: left = mid + 1
            elif acc <= threshold: right = mid
        return left


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        # O(n*log(sum(nums)))
        
        
        # sum = 18, threshold = 6, left = 0, right = 3
        
        l = 1
        r = max(nums)
        while l < r:
            m = l + (r - l) // 2
            # print(l, r)
            s = sum([ceil(x/m) for x in nums])
            # print(\"sum: \", s)
            if s > threshold:
                l = m + 1
            else:
                r = m
        
        return l
                
        
        


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        l = 0
        r = nums[-1]
        res = []
        while r-l > 1:
            c = (l+r)//2
            tmp_sum = [math.ceil(i/c) for i in nums]
            tmp_sum = sum(tmp_sum)
            if tmp_sum > threshold:
                l = c
            elif tmp_sum <= threshold:
                r=c
                res.append(c)
        return min(res)
            


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        l, r = 1, max(nums)
        count = 0
        while l < r:
            m = l + (r-l)//2
            for i in nums:
                count += (i + m -1) // m
            if count > threshold:
                l = m + 1
            else:
                r = m
            count = 0
        return l
        


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        nums.sort()
        n = len(nums)
        
        start, end = 1, nums[-1]
        while start < end:
            mid = (start + end) // 2
            j = n - 1
            s = n
            while j >= 0 and mid < nums[j]:
                s -= 1
                s += math.ceil(nums[j] / mid)
                j -= 1
            if s > threshold:
                start = mid + 1
            else:
                end = mid
        return start
        # j = len(nums) - 1
        # for i in nums[::-1]:
        #     j = n - 1
        #     s = n
        #     while j >= 0 and i < nums[j]:
        #         s -= 1
        #         s += math.ceil(nums[j] / i)
        #         j -= 1
        #     if s > threshold:
        #         start = i
        #         end = prev
        #         break
        #     prev = i
        # else:
        #     start = 1
        #     end = i
        # # print(start, end)   
        # for i in range(end, start - 1, -1):
        #     j = n - 1
        #     s = n
        #     while j >= 0 and i < nums[j]:
        #         s -= 1
        #         s += math.ceil(nums[j] / i)
        #         j -= 1
        #     if s > threshold:
        #         return i + 1
        # return 1


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def condition(arr, thr, div):
            res = 0
            for i in arr:
                res += math.ceil(i/div)
            return res <= thr
                
        
        l, r = 1, max(nums)
        while l < r:
            m = l + (r-l)//2
            if condition(nums, threshold, m):
                r = m
            else:
                l = m + 1
            
        return l

import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        small, big = 1, max(nums)
        while small < big:
            mid = small + (big-small)//2
            cur = 0
            for num in nums:
                cur += math.ceil(num/mid)
            if cur > threshold:
                small = mid + 1
            else:
                big = mid
        return small

import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:

#         left, right = 1, max(nums)
#         while left + 1 < right:
#             mid = (left + right) // 2
#             div_sum =  self.get_sum(mid, nums)
#             if div_sum > threshold:
#                 left = mid
#             else:
#                 right = mid
        
#         div_sum = self.get_sum(left, nums)
#         if div_sum <= threshold:
#             return left
#         return right
        
    
#     def get_sum(self, divisor, nums):
#         res = 0
#         for n in nums:
#             tmp = n // divisor
#             if tmp * divisor < n:
#                 tmp += 1
            
#             res += tmp
        
#         return res
    
        def chk(nmb):
            if nmb == 0:
                return False
            val = 0
            for num in nums:
                val += math.ceil(num/nmb)
                if val > threshold:
                    return False
            return True
            
        high = sum(nums)
        low = math.ceil(high/threshold)  
        while low <= high:
            mid = (low + high)//2
            
            if chk(mid):
                high = mid - 1
            elif not chk(mid):
                low = mid + 1
        return low-1 if chk(low-1) else high+1
                


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

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def getSum(k):
            res = 0
            for n in nums:
                if n % k == 0:
                    res += n // k
                else:
                    res += n // k + 1
            return res
            
        l, r = max(sum(nums) // threshold, 1), max(1, sum(nums))
        while l < r:
            m = (l + r) // 2
            if getSum(m) > threshold:
                l = m + 1
            else:
                r = m
        return l

import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:

#         left, right = 1, max(nums)
#         while left + 1 < right:
#             mid = (left + right) // 2
#             div_sum =  self.get_sum(mid, nums)
#             if div_sum > threshold:
#                 left = mid
#             else:
#                 right = mid
        
#         div_sum = self.get_sum(left, nums)
#         if div_sum <= threshold:
#             return left
#         return right
        
    
#     def get_sum(self, divisor, nums):
#         res = 0
#         for n in nums:
#             tmp = n // divisor
#             if tmp * divisor < n:
#                 tmp += 1
            
#             res += tmp
        
#         return res
    
        def chk(nmb):
            if nmb == 0:
                return False
            val = 0
            for num in nums:
                val += math.ceil(num/nmb)
                if val > threshold:
                    return False
            return True
            
        high = sum(nums)
        low = (high//threshold)  
        while low <= high:
            mid = (low + high)//2
            
            if chk(mid):
                high = mid - 1
            elif not chk(mid):
                low = mid + 1
        return low-1 if chk(low-1) else high+1
                


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        l = 1
        u = max(nums)
        
        def division_sum(k):
            return sum(int(math.ceil(n/k)) for n in nums)
        
        while l < u:
            mid = l + (u-l)//2
            
            if division_sum(mid) <= threshold:
                u = mid
            else:
                l = mid + 1
        
        return l

import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def condition(divisor):
            return sum((num - 1) // divisor +1 for num in nums) <= threshold
        left, right = 1, max(nums)
        while left < right:
            mid = left + (right -left) //2
            if condition(mid):
                right = mid
            else:
                left = mid + 1
        return left

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        '''
        
        find m where    (num + m) // m    for all nums and sum to <= threshold
        
        '''
        
        i = 1
        j = max(nums)
        m = (i + j) // 2
        
        ans = 0
        
        while i <= j:
            
            total = 0
            for num in nums:
                total += (num + m - 1) // m  # ceil. division
                
            if total > threshold:
                i = m + 1
            elif total <= threshold:
                j = m - 1
                ans = m
            
            m = (i + j) // 2  # mid point
        
        return ans

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        '''
        
        find m where    (num + m) // m    for all nums and sum to <= threshold
        
        '''
        
        i = 1
        j = max(nums)
        
        while i < j:
            m = (i + j) // 2
            
            total = 0
            for num in nums:
                total += (num + m - 1) // m  # ceil. division
                
            if total > threshold:
                i = m + 1
            elif total <= threshold:
                j = m
        
        return i

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        l = 1
        r = max(nums)
        
        while l < r:
            
            m = (l + r) // 2
            
            if sum((n + m - 1) // m for n in nums) > threshold:
                l = m + 1
            else:
                r = m
                
        return l

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        def feasible(div):
            count = 0
            for num in nums:
                count += (num-1)//div + 1
            return count<=threshold
        
        left = 1
        right = max(nums)
        
        while left < right:
            mid = left + ((right-left)>>1)
            if feasible(mid):
                right = mid
            else:
                left = mid+1
        return left

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        #def evl(d):
            #s = 0
            #for n in nums:
            #    s += (n-1) // d + 1
            #return s
        #    return 
        
        def BS(p, r):
            

            if r-p <= 1:
                if sum([(n-1)//p + 1 for n in nums]) <= threshold:
                    return p
                return r
            
            q = (r+p)//2
            
            e = sum([(n-1)//q + 1 for n in nums])
            if e <= threshold:
                return BS(p, q)
            else:
                return BS(q, r)
        
        
        r = max(nums)
        p = 1
        
        return BS(p,r)


from numpy import array, ceil, sum
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        ''' Original solution
        def div(a,b):
            return (a//b + 1 - (a//b == a/b))
        
        divisor = max(nums)//2
        divided_list = [div(num, divisor) for num in nums]
        
        left = 1
        right = max(nums)
        while right - left > 1:
            
            goleft = (sum(divided_list) <= threshold)
            
            if goleft:
                right = divisor
                divisor = (divisor + left) // 2
                
            else:
                left = divisor
                divisor = (divisor + right) // 2
            
            #print(f\"left:{left}, right:{right}\")
            
            divided_list = [div(num, divisor) for num in nums]

        if sum(divided_list) > threshold:
            divisor += 1
        
        return divisor'''
        
        nums = array(nums)
        l, r = int(ceil(sum(nums)/threshold)), max(nums)
        
        while l < r:
            mid = (l+r)//2
            if sum(ceil(nums/mid)) <= threshold:
                r = mid
            else:
                l = mid + 1
        
        return r

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        low,high = 1, max(nums)
        
        while low<high:
            
            mid = (low+high)//2
            
            if(sum(ceil(elem/mid) for elem in nums)) > threshold:
                low = mid +1
            
            else:
                high = mid
        
        return low

from math import ceil
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        l, r = 1, max(nums)
        while l < r:
            d = (l+r) // 2
            s = sum ( [ ceil(n/d) for n in nums ])
            if s>threshold:
                l = d+1
            else:
                r = d
        return l 


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        mx = max(nums)

        low = 1
        high = mx
        best = mx

        while low < high:
            med = low + (high-low) // 2

            total = 0

            for num in nums:
                total += ceil(num / med)

            if total <= threshold:
                high = med
                best = min(best,med)
            else:
                low = med + 1


        return best


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        low, high = 1, max(nums)
        while low <= high:
            mid = (low + high)//2
            total = 0
            for num in nums:
                total += ceil(num/mid)
            if total > threshold:
                low = mid + 1
            else:
                high = mid - 1
        return low

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        # high = math.ceil(max(nums) * len(nums) / threshold)
        # low = math.ceil(sum(nums) / threshold)
        low, high = math.ceil(sum(nums)/threshold), math.ceil(sum(nums)/(threshold-len(nums)))
        def binary_search(low, high): 
            if high > low: 
                mid = (high + low) // 2
                tot = 0
                for num in nums:
                    tot += math.ceil(num / mid)
                if tot <= threshold: 
                    return binary_search(low, mid)  
                else: 
                    return binary_search(mid + 1, high) 
            else: 
                return high
        return binary_search(low, high)

from math import ceil
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        left=1
        right=max(nums)
        def cal_sum(div):
            div_sum=0
            for num in nums:
                div_sum+=ceil(num/div)
            return div_sum
        while left< right:
            mid=left+(right-left)//2
            if cal_sum(mid)>threshold:
                left=mid+1
            else:
                right=mid
        
                
                
        return right
        


from math import ceil
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        left=1
        right=max(nums)
        def cal_sum(div):
            div_sum=0
            for num in nums:
                div_sum+=ceil(num/div)
            return div_sum
        while left< right:
            mid=left+(right-left)//2
            if cal_sum(mid)>threshold:
                left=mid+1
            else:
                right=mid
        
                
                
        return left
        


from bisect import bisect_left

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        hi = math.ceil(len(nums) * max(nums) / threshold)
        lo = math.ceil(sum(nums) / threshold)
        
        while lo <= hi:
            med = (lo + hi) // 2
            cur = self.divSum(nums, med)
            if cur <= threshold:
                hi = med - 1
            else:
                lo = med + 1
        
        return lo
            
    def divSum(self, nums, div):
        total = 0
        for num in nums:
            total += math.ceil(num / div)
        return total

import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def division(divisor):
            total = 0
            for n in nums:
                total += math.ceil(n / divisor)
            return total
        
        total = sum(nums)
        left = max(1, total//threshold)
        right = math.ceil(total/(threshold-len(nums)))
        while left < right:
            mid = (left + right) // 2
            if division(mid) > threshold:
                left = mid + 1
            else:
                right = mid
        return left


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        left, right = 1, max(nums)
        
        while left < right:
            mid = left + (right-left)//2
            
            total = sum([(x + mid - 1)//mid for x in nums])
            
            if total > threshold:
                left = mid + 1
            else:
                right = mid
                
        return left


from numpy import array, ceil, sum
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        nums = array(nums)
        l, r = 1, max(nums)
        while l < r:
            mid = (l+r)//2
            if sum(ceil(nums / mid)) <= threshold:
                r = mid
            else:
                l = mid + 1
        return r   
        
        
        
        
        
        


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

from math import ceil

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        left, right = 1, max(nums)
        while left <= right:
            m = left + (right - left) // 2
            if self.check(nums, m, threshold):
                ans = m
                right = m - 1
            else:
                left = m + 1
        return ans
    
    def check(self, nums, m, threshold):
        return sum([ceil(x/m) for x in nums]) <= threshold
    


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        high = math.ceil(max(nums) * len(nums) / threshold)
        low = math.ceil(sum(nums) / threshold)
        while high > low: 
            mid = (high + low) // 2
            tot = 0
            for num in nums:
                tot += math.ceil(num / mid)
            if tot <= threshold: 
                high = mid  
            else: 
                low = mid + 1
        return high


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def helper(div):
            output = 0
            for n in nums:
                if n % div == 0:
                    output += n//div
                else:
                    output += n//div+1
            if output <= threshold: return True
            return False
    
        nums.sort()
        l, r = 1, max(nums)
        while l < r:
            mid = l + (r-l)//2
            if helper(mid):
                r = mid
            else:
                l = mid + 1
        return l

import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        # No matter what each num must contribute at least 1 (even if the divisor is infinite)
        # We need to binary search divisor range from 1 to max(nums), since the lowest divisor possible is dividing by 1, and the highest divisor we can use is the max of nums, so everything will divide to 1
        
        
        left = 1
        right = max(nums)
        
        while left <= right:
            mid = (left + right) // 2
            sum_val = sum(math.ceil(num / mid) for num in nums)
            if sum_val <= threshold: # We want to divide by a smaller num
                right = mid - 1
            else:
                left = mid + 1
            # Left will stop at the lowest divisor that makes sum_val <= threshold
        return left


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        L, R = 1, max(nums)+1
        
        def solve(divisor):
            sums = 0
            for num in nums:
                sums += num // divisor
                sums += 0 if num % divisor == 0 else 1
            
            return sums > threshold
        
        while L < R:
            mid = L + (R-L) // 2
            if solve(mid):
                L = mid + 1
            else:
                R = mid
                
        return R

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        a = 1
        b = max(nums)
        i = (a+b)//2
        ans = 10000000000000
        while b-a >1:
            sum = 0
            for j in nums:
                if j%i == 0:
                    sum += j//i
                else:
                    sum += j//i + 1
            if sum <= threshold:
                ans = min(i,ans)
                b = i
            else:
                a = i
            i = (a+b)//2
        for i in(a,b):
            sum = 0
            for j in nums:
                if j%i == 0:
                    sum += j//i
                else:
                    sum += j//i + 1
            if sum <= threshold:
                ans = min(i,ans)  
        return ans

import math

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        low, high = 1, max(nums)
        while low < high:
            mid = (low+high)//2
            if sum(math.ceil(num/mid) for num in nums) > threshold:
                low = mid + 1
            else:
                high = mid
        return low


import numpy as np

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        nums = np.array(nums)
        left = sum(nums) // threshold
        right = max(nums) + 1
        
        while left < right:
            mid = left + (right - left) // 2

            if np.sum(np.ceil(nums / mid)) <= threshold:
                right = mid
            else:
                left = mid + 1
        return left
        


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        L, R = 1, max(nums)+1
        
        def solve(divisor):
            res = []
            for num in nums:
                res.append(num // divisor + (0 if num % divisor == 0 else 1))
            
            return sum(res) > threshold
        
        while L < R:
            mid = L + (R-L) // 2
            if solve(mid):
                L = mid + 1
            else:
                R = mid
                
        return R

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

class Solution:
    
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        low = 1
        high = 2 * max(nums)
        ans = float('inf')
        
        while low <= high:
            mid = (low + high) // 2
            m = sum(math.ceil(x/mid) for x in nums)
            if m <= threshold:
                ans = min(ans, mid)
                high = mid - 1
            else:
                low = mid + 1
        
        return ans

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        s = sum(nums)
        lo = max(1, s // threshold)
        hi = max(nums)
        
        while lo < hi:
            mid = (lo + hi) // 2
            r = sum([math.ceil(n / mid) for n in nums])
            if r > threshold:
                lo = mid + 1
            else:
                hi = mid
                
        return lo

import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:

        def get_sum(nmb):
            if nmb == 0:
                return False
            val = 0
            for num in nums:
                val += math.ceil(num/nmb)
            return val 
        
        left, right = 1, max(nums)
        while left <= right:
            mid = (left + right) // 2 
            if get_sum(mid) > threshold:
                left = mid+1
            else:
                right = mid-1

        return right+1 if get_sum(right+1) else right
    
       
    
#     def get_sum(self, divisor, nums):
#         res = 0
#         for n in nums:
#             tmp = n // divisor
#             if tmp * divisor < n:
#                 tmp += 1
            
#             res += tmp
        
#         return res
    
#         def chk(nmb):
#             if nmb == 0:
#                 return False
#             val = 0
#             for num in nums:
#                 val += math.ceil(num/nmb)
#                 if val > threshold:
#                     return False
#             return True
            

                


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def get_sum(d):
            ans = 0
            for n in nums:
                ans += math.ceil(n/d)
            return ans
        
        l, r = 1, max(nums)
        ans = 0
        
        while l < r:
            m = (l + r) // 2
            test = get_sum(m)
            if test <= threshold:
                ans = m
                r = m
            else:
                l = m + 1
        return l
    


from numpy import array, ceil

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        nums = array(nums)
        l, r = 1, max(nums)
        while l < r:
            mid = (l+r)//2
            if sum(ceil(nums / mid)) <= threshold:
                r = mid
            else:
                l = mid + 1
        return r

import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:

        def get_sum(nmb):
            if nmb == 0:
                return False
            val = 0
            for num in nums:
                val += math.ceil(num/nmb)
            return val 
        
        left, right = 1, max(nums)
        while left <= right:
            mid = (left + right) // 2 
            if get_sum(mid) > threshold:
                left = mid+1
            else:
                right = mid-1

        if get_sum(left) <= threshold:
            return left
        return right
    
       
    
#     def get_sum(self, divisor, nums):
#         res = 0
#         for n in nums:
#             tmp = n // divisor
#             if tmp * divisor < n:
#                 tmp += 1
            
#             res += tmp
        
#         return res
    
#         def chk(nmb):
#             if nmb == 0:
#                 return False
#             val = 0
#             for num in nums:
#                 val += math.ceil(num/nmb)
#                 if val > threshold:
#                     return False
#             return True
            
#         high = max(nums)
#         low = high//threshold 
#         while low <= high:
#             mid = (low + high)//2
            
#             if chk(mid):
#                 high = mid - 1
#             elif not chk(mid):
#                 low = mid + 1
#         return low-1 if chk(low-1) else high+1
                


import numpy as np
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        Nums = np.array(nums)
        low = 1
        high = np.max(Nums)
        min_num = np.max(Nums)
        Sum = 0
        while low <= high:
            mid = np.ceil((low + high) / 2)
            Sum = np.sum(np.ceil(Nums/mid))
            if Sum <= threshold:
                min_num = mid
                high = mid - 1
            else:
                low = mid + 1
        return int(min_num)
    


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        l = 1
        r = max(nums)
        
        def helper(arr,mid,threshold):
            return sum([math.ceil(num/mid) for num in arr])<=threshold
        
        while l<=r:
            mid = (l+r)//2
            if helper(nums,mid,threshold):
                r = mid-1
            else:
                l = mid+1
        return l

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        left, right = 1, max(nums)
        while left < right:
            mid = left + (right - left) // 2
            divided = sum([num//mid + int(num%mid > 0) for num in nums])
            # print(mid, divided, threshold)
            if divided > threshold:
                left = mid + 1
            else:
                right = mid
        return right


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        low=1
        high=max(nums)
        n=len(nums)
        while(low<high):
            mid=low+(high-low)//2
            s=0
            for i in range(n):
                
                s+=math.ceil(nums[i]/mid)
            if(s>threshold):
                low=mid+1
            else:
                high=mid
        return high  


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def enough(x):
            cnt = 0
            for num in nums:
                cnt += int(num//x) + (num%x > 0)
            return cnt <= threshold
        
        left, right = 1, max(nums)
        while left < right:
            mid = (left + right) // 2
            if enough(mid):
                right = mid
            else:
                left = mid+1
        return left

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        def calculate(divisor):
            _sum=0
            for val in nums:
                _sum+=val//divisor + int(val%divisor!=0)
            return _sum
        
        
        start,end=1,max(nums)
        while start<end:
            mid=start+(end-start)//2
            _sum=calculate(mid)
            if _sum>threshold:
                start=mid+1
            else:
                end=mid
        return start
            


import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def ok(mid):
            ans = 0
            for num in nums:
                ans += math.ceil(num / mid)
                if ans > threshold: return False
            return True    
        l, r = 1, int(1e6)
        while l <= r:
            mid = (l+r) // 2
            if ok(mid): r = mid - 1
            else: l = mid + 1
        return l        
#         nums.sort()
        
#         v1 = sum(nums)
#         v2 = len(nums)
#         if v1<= threshold:
#             return 1
#         l = 1
#         u = max(nums)
        
#         addl = []
#         while l+1<u: 
#             print(l,u)
#             mid = (l+u)//2  
#             print('mid',mid)
#             add = 0
#             for i in range(len(nums)):
#                 add = add + math.ceil(nums[i]/mid) 
#             print(add)
            
#             if add>threshold:
#                 l = mid
#             elif add == threshold:
#                 return mid
#             else:
#                 addl.append(mid)
#                 u = mid
                
#         return min(addl
    
    
                
                
                
                
            
            
        


import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        # max = 0
        # for j in range(threshold):
        #     count = 0
        #     for i in range(len(nums)):
        #         a = nums[i]/(j+1)
        #         count += math.ceil(a)
        #     print(count)
        #     if count <= threshold:
        #         if max < count:
        #             max = count
        # return j
        def checking(mid):
            ans = 0
            for num in nums:
                ans += math.ceil(num/mid)
                if ans > threshold:
                    return False
            return True
        l, r = 1, int(1e6)
        while l<= r:
            mid = (l+r)//2
            if checking(mid):
                r = mid-1
            else:
                l = mid+1
        return l


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        #res=sum(nums)
        #print(1//5)
        #n=max(nums)+1
        #print(int(1e6))
        def dfs(m):
            r=0
            for i in nums:
                r+=math.ceil(i/m)
                if r>threshold:
                    return False
            return True
        l,r=1,int(1e6)
        while l<=r:
            m=(l+r)//2
            if dfs(m):
                r=m-1
            else:
                l=m+1
        return l
        '''
        for i in range(1,max(nums)):
            r=0
            n-=1
            for j in nums:
                if j%i==0:
                    r+=j//i
                else:
                    r+=(j//i)+1
            if r<=threshold:
                return i
        '''
        #return res


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        r = max(nums)
        l = 1
        
        def calc(div):
            s = sum([(num + div - 1) // div for num in nums])
            return s <= threshold
        
        while l < r:
            mid = (l + r) // 2
            val = calc(mid)
            # print (\"[%d, %d] => %d v %r\" %(l, r, mid, val))
            
            if calc(mid):
                r = mid
            else:
                l = mid + 1
        
        return l
                
        


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def bs(mid):
            sum_val = 0
            for i in nums:
                sum_val+=math.ceil(i/mid)
                if sum_val > threshold:
                    return False
            return True
        l =1
        r = 10**6
        while l<=r:
            mid = (l+r)//2
            if bs(mid):
                r = mid-1
            else:
                l=mid+1
        return l


from numpy import array, ceil, sum
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        nums = array(nums)
        l, r = 1, max(nums)
        while l < r:
            mid = (l+r)//2
            if sum(ceil(nums / mid)) <= threshold:
                r = mid
            else:
                l = mid + 1
        return r


import math
def divisor(l, n):
    ans = 0
    
    for i in l:
        ans += math.ceil(i/n)
    return ans


class Solution:
    def smallestDivisor(self, l: List[int], t: int) -> int:
        if sum(l)<=t:
            return 1
        s = sum(l)
        ans = 0
        x = 0
        i = 1
        j = 1
        while(x<t):
            j = i
            x = divisor(l, i)
            if x<t:
                i *= 2 
            else:
                break
        mid = 0
        j = max(l)
        p = -1
        # print(i, j)
        
        while(i<j):
            
            mid = (i+j)//2
            x = divisor(l, mid)
            # print('mid',x, mid)                
            if x<t:
                j = mid
            elif x == t:
                break
            else:
                i = mid+1
            if i == j:
                mid = j
                break
        
        while(1):
            # print(mid)
            x = divisor(l, mid-1)
            if x <= t:
                mid -= 1
            else:
                break
                
        return mid
                
                        
        
        


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def ok(mid):
            ans = 0
            for num in nums:
                ans += math.ceil(num / mid)
                if ans > threshold: return False
            return True    
        l, r = 1, int(1e6)
        while l <= r:
            mid = (l+r) // 2
            if ok(mid): r = mid - 1
            else: l = mid + 1
        return l    

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def check(div):
            # print(sum([elem/div if elem % div == 0 else (elem//div)+1 for elem in nums]))
            return threshold >= sum([elem/div if elem % div == 0 else (elem//div)+1 for elem in nums])
        
        def bst(low,high):
            # print(low,high)
            mid = (low+high) // 2
            if low > high:
                return -1
            elif low == high:
                if check(low):
                    return low
                else:
                    return -1
            else:
                if check(mid):
                    ambition = bst(low,mid-1)
                    if ambition != -1:
                        return ambition
                    else:
                        return mid
                else:
                    return bst(mid+1,high)
                
        return bst(1,10**9)


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        start = 1
        end = max(nums)
        
        while start <= end:
            mid = (start + end) // 2
            result = self.satistfy(nums, mid)

            if result <= threshold:
                end = mid - 1
            else:
                start = mid + 1

        return start
    
    def satistfy(self, nums, mid):
        return sum(list([math.ceil(x/mid) for x in nums]))
        


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        start = 1
        end = max(nums)
        
        while start+1 < end:
            mid = (start + end) // 2
            result = sum(list([math.ceil(x/mid) for x in nums]))

            if result <= threshold:
                end = mid
            else:
                start = mid

        if sum(list([math.ceil(x/start) for x in nums])) <= threshold:
            return start
        return end
        


import math

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        if not nums:
            return sys.maxsize
        left, right = 1, 2
        while right < sys.maxsize and self.get_sum(nums, right) > threshold:
            left, right = right, right * 10

        
        while left + 1 < right:
            mid = (left + right) // 2
            if self.get_sum(nums, mid) <= threshold:
                right = mid
            else:
                left = mid
        if self.get_sum(nums, left) <= threshold:
            return left
        return right
    
    def get_sum(self, nums: List[int], divisor: int) -> int:
        result = 0
        for num in nums:
            result += math.ceil(num / divisor)
        return int(result)

import math

def divide_and_sum(nums, divisor):
    return sum([math.ceil(x / divisor) for x in nums])

class Solution:
    def smallestDivisor(self, nums, threshold):
        start = max(nums)
        end = 1

        assert divide_and_sum(nums, start) <= threshold, 'impossible, threshold is guaranteed to be at least len(nums)'
        if divide_and_sum(nums, end) <= threshold:
            # there are no divisors smaller than 1
            return end

        # loop invariant:
        # dsum(nums, start) <= threshold
        # dsum(nums, end)   > threshold
        while start >= end:
            mid = (start + end) // 2
            dsum = divide_and_sum(nums, mid)
            if dsum == threshold:
                #print('case 1')
                while divide_and_sum(nums, mid) == threshold:
                    mid -= 1
                return mid + 1
            if dsum > threshold:
                # divisor is too small
                end = mid + 1
            if dsum < threshold:
                # threshold is too large
                start = mid - 1
        #print('case 2')
        return end


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        start = 1
        end = max(nums)
        
        while start+1 < end:
            mid = (start + end) // 2
            result = self.satistfy(nums, mid)

            if result <= threshold:
                end = mid
            else:
                start = mid

        if self.satistfy(nums, start) <= threshold:
            return start
        return end
    
    
    def satistfy(self, nums, mid):
        return sum(list([math.ceil(x/mid) for x in nums]))
        


'''
Binary search to find the best divisor that doesn't go through the threshold
'''
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        def ok(divisor):
            sol = 0
            for n in nums:
                sol += ceil(n / divisor)
            return sol <= threshold
                
        lo = 1
        hi = max(nums)
        while lo <= hi:
            mid = (lo + hi) // 2
            # if current is okay, we have to go higher lower
            if ok(mid):
                hi = mid - 1
            else:
                lo = mid + 1
        return lo
                
                
            
            
    


from numpy import array, ceil, sum
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        nums = array(nums)
        l, r = int(ceil(sum(nums)/threshold)), max(nums)
        
        while l < r:
            mid = (l+r)//2
            if sum(ceil(nums/mid)) <= threshold:
                r = mid
            else:
                l = mid + 1
        
        return r

import math

def divide_and_sum(nums, divisor):
    return sum([math.ceil(x / divisor) for x in nums])

class Solution:
    def smallestDivisor(self, nums, threshold):
        start = max(nums)
        end = 1

        assert divide_and_sum(nums, start) <= threshold, 'impossible, threshold is guaranteed to be at least len(nums)'
        if divide_and_sum(nums, end) <= threshold:
            # there are no divisors smaller than 1
            return end

        # loop invariant:
        # dsum(nums, start) <= threshold
        # dsum(nums, end)   >= threshold
        while start >= end:
            mid = (start + end) // 2
            dsum = divide_and_sum(nums, mid)
            if dsum == threshold:
                #print('case 1')
                mid -= 1
                while divide_and_sum(nums, mid) == threshold:
                    mid -= 1
                return mid + 1
            if dsum > threshold:
                # divisor is too small
                end = mid + 1
            if dsum < threshold:
                # threshold is too large
                start = mid - 1
        #print('case 2')
        #loop exit condition:
        #start < end
        #dsum(nums, start) <= threshold
        #dsum(nums, end)   >= threshold
        print((start, end, divide_and_sum(nums, start), divide_and_sum(nums, end)))
        return end


import math
class Solution:
    def smallestDivisor(self, nums: List[int], t: int) -> int:
        def mine2(n,nums):
            nums_copy = nums[:]
            nums_copy = list([math.ceil(x/n) for x in nums_copy])
            return sum(nums_copy)
        def mine(left,right,nums,t,l):
            if(right>left):
                mid = (left+right)//2
                if(mine2(mid,nums)<=t):
                    right = mid-1
                    l.append(mid)
                else:
                    left = mid+1
                return mine(left,right,nums,t,l)
            else:
                if(left>0):
                    if(mine2(left,nums)<=t):
                        l.append(left)
                if(right>0):
                    if(mine2(right,nums)<=t):
                        l.append(right)
                return l
                
                
                
        
        l = []
        return min(mine(1,max(nums),nums,t,l))


# Binary Search
import math

class Solution:
    def smallestDivisor(self, nums, threshold):

        nums.sort()
        # you can take hi=10^6 as well
        # but hi=max_element, will also be correct
        # because nums.length <= threshold
        ans = float('+INF')
        lo, hi = 1, nums[-1]
        while lo<=hi:
            mid = lo + (hi-lo)//2
            if self.div(nums, mid) <= threshold:
                ans = min(ans, mid)
                hi = mid-1
            else:
                lo = mid+1
        
        return ans

    def div(self, nums, mid):
        t_sum=0
        for i in nums:
            t_sum += int(math.ceil(i/mid))
        return t_sum




class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        # sm = sum(nums)
        # strt = sm//threshold
        
        # search_space = list(range(max(strt,1),sm))
        # n = len(search_space)
        l = 1
        r = max(nums)
        while(l+1<r):
            mid = l+(r-l)//2
            
            # if self.search(nums,search_space[mid],threshold)  == 0:
            #     return search_space[mid]
            if self.search(nums,mid,threshold) > 0:
                r = mid
            elif self.search(nums,mid,threshold) < 0:
                l = mid
        
        # print(search_space[l],search_space[r])
        if self.search(nums,l,threshold) >= 0:
            return l
        else:
            return r
        # print(search_space[l],search_space[r])
            
        
            
            
    def search(self,nums,i,threshold):
    
        insum = sum([math.ceil(el/i) for el in nums])
        # print(i,insum)
        
        # if insum == threshold:
        #     return 0
        if insum <= threshold:
            return 1
        else:
            return -1
            


class Solution:
    
    def check(self,divisor,nums,threshold):
        result = 0
        for number in nums:
            k = int(number/divisor)
            if number % divisor != 0:
                k +=1
            result += k
            if result > threshold:
                return False
        return True
        
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        low = 1
        high = max(nums)
        while low <= high:
            mid = int((low+high)/2)
            if self.check(mid,nums,threshold):
                high = mid -1
            else:
                low = mid+1
        return low


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        sm = sum(nums)
        # strt = sm//threshold
        
        # search_space = list(range(max(strt,1),sm))
        # n = len(search_space)
        l = max(sm//threshold,1)
        r = max(nums)
        while(l+1<r):
            mid = l+(r-l)//2
            
            if self.search(nums,mid,threshold) > 0:
                r = mid
            elif self.search(nums,mid,threshold) < 0:
                l = mid+1
        
        if self.search(nums,l,threshold) >= 0:
            return l
        else:
            return r
        # print(search_space[l],search_space[r])
            
        
            
            
    def search(self,nums,i,threshold):
    
        insum = sum([math.ceil(el/i) for el in nums])
        if insum <= threshold:
            return 1
        else:
            return -1
            


class Solution:
    def divide(self, num, divisor):
        return -((-num)//divisor)
    
    def getQuotient(self, nums, divisor):
        output = 0
        for num in nums:
            output += self.divide(num, divisor)
        return output
    
    def getResult(self, results, divisor, nums):
        if divisor in results:
            return results[divisor]
        else:
            results[divisor] = self.getQuotient(nums, divisor)
            return results[divisor]
    
    def helper(self, results, nums, i, j, threshold):
        if i == j:
            return i
        
        mid = (i+j)//2
        if mid == 1:
            return mid
        elif self.getResult(results, mid, nums) <= threshold and self.getResult(results, mid-1, nums) > threshold:
            return mid
        elif self.getResult(results, mid, nums) <= threshold:
            return self.helper(results, nums, i, mid-1, threshold)
        else:
            return self.helper(results, nums, mid+1, j, threshold)
    

    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        maxDivisor = self.divide(2*sum(nums), threshold)
        #print(maxDivisor)
        #maxDivisor = 1000000
        results = dict()
        
        return self.helper(results, nums, 1, maxDivisor, threshold)


import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:

        def chk(nmb):
            if nmb == 0:
                return False
            val = 0
            for num in nums:
                val += math.ceil(num/nmb)
            return val <= threshold
        
        high = max(nums)
        low = high//threshold 
        while low <= high:
            mid = (low + high)//2
            
            if chk(mid):
                high = mid - 1
            elif not chk(mid):
                low = mid + 1
        return high+1 if chk(high+1) else high
    
       
    
#     def get_sum(self, divisor, nums):
#         res = 0
#         for n in nums:
#             tmp = n // divisor
#             if tmp * divisor < n:
#                 tmp += 1
            
#             res += tmp
        
#         return res
    
#         def chk(nmb):
#             if nmb == 0:
#                 return False
#             val = 0
#             for num in nums:
#                 val += math.ceil(num/nmb)
#                 if val > threshold:
#                     return False
#             return True
            

                


from math import ceil

def eval(nums, i, thold):
    s1 = 0
    for num in nums:
        s1 += ceil(num / i)
    if s1 <= thold:
        return True
    return False

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        lo, hi = 1, 100000000000
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if eval(nums, mid, threshold):
                hi = mid
            else:
                lo = mid + 1
        return lo


# class Solution:
#     def smallestDivisor(self, nums: List[int], threshold: int) -> int:

#         def check(divisor):
#             res = 0
#             for num in nums:
#                 if num % divisor == 0:
#                     res += num // divisor
#                 else:
#                     res += (num // divisor) + 1
#             if res <= threshold:
#                 return True
#             return False
        
#         left = 1
#         right = 1000000 #最大元素700ms
#         # right = 1 800ms
#         # for num in nums:
#         #     right = max(right, num)
#         while left < right:
#             mid = (left + right) >> 1
#             if check(mid) == True:
#                 right = mid
#             else:
#                 left = mid+1
                
#         return left

from numpy import array, ceil, sum
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        nums = array(nums)
        l, r = 1, max(nums)
        while l < r:
            mid = (l+r)//2
            if sum(ceil(nums / mid)) <= threshold:
                r = mid
            else:
                l = mid + 1
        return r

import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        self.nums = nums
        self.threshold = threshold
        num_sum = sum(nums)
        l = math.floor(num_sum / threshold)-1
        h = num_sum
        m = math.ceil((l+h) / 2)
        while h != m:
            if self.validate_divisor(m):
                h = m
            else:
                l = m
            m = math.ceil((l+h) / 2)
        return h
        
    def validate_divisor(self, divisor):
        if divisor <= 0:
            return False
        s = sum(math.ceil(x / divisor) for x in self.nums)
        return s <= self.threshold

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def isThres(m):
            tsum = 0
            for n in nums:
                tsum += n // m
                if n % m > 0:
                    tsum += 1
            if tsum <= threshold:
                return True
        
        
        l,r = 1, sum(nums)
        
        while l < r:
            m = l + r >> 1
            if isThres(m):
                r = m
            else:
                l = m + 1
        
        return l

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        # binary search
        left = 1
        right = max(nums)
        while left <= right:
            mid = left + (right - left) // 2
            mid_left_result = self.divide_and_sum(mid - 1, nums)
            mid_result = self.divide_and_sum(mid, nums)
            if mid_left_result > threshold and mid_result <= threshold:
                return mid
            # move right
            if mid_result > threshold:
                left = mid + 1
            # move left
            if mid_left_result <= threshold:
                right = mid - 1

    def divide_and_sum(self, divisor, nums):
        if divisor == 0:
            return math.inf

        result = 0
        for num in nums:
            result += ceil(num / divisor)

        return result

import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:

#         left, right = 1, max(nums)
#         while left + 1 < right:
#             mid = (left + right) // 2 
#             if self.get_sum(mid, nums) > threshold:
#                 left = mid
#             else:
#                 right = mid

#         if self.get_sum(left, nums) <= threshold:
#             return left
#         return right
    
#     def get_sum(self, nmb, nums):
#         if nmb == 0:
#             return False
#         val = 0
#         for num in nums:
#             val += math.ceil(num/nmb)
#         return val        
    
#     def get_sum(self, divisor, nums):
#         res = 0
#         for n in nums:
#             tmp = n // divisor
#             if tmp * divisor < n:
#                 tmp += 1
            
#             res += tmp
        
#         return res
    
        def chk(nmb):
            if nmb == 0:
                return False
            val = 0
            for num in nums:
                val += math.ceil(num/nmb)
                if val > threshold:
                    return False
            return True
            
        high = max(nums)
        low = high//threshold 
        while low <= high:
            mid = (low + high)//2
            
            if chk(mid):
                high = mid - 1
            elif not chk(mid):
                low = mid + 1
        return low-1 if chk(low-1) else high+1
                


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def is_valid(select_num: int):
            res = sum([math.ceil(num / select_num) for num in nums])
            return None if res > threshold else res
        
        if not nums: return 0
        left, right = 1, 1000000000
        while left < right:
            middle = (left + right) // 2
            if is_valid(middle):
                right = middle
            else:
                left = middle + 1
        
        return left if is_valid(left) else right


class Solution:
    
    def find(self, nums, div):
        ans = 0
        for i in nums:
            ans += i//div
            if i%div!=0:
                ans += 1
        return ans
    
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        low = 1
        high = max(nums)
        while low<high:
            mid = (low+high)//2
            cur = self.find(nums, mid)
            if mid>1:
                prev = self.find(nums, mid-1)
            else:
                prev = 0
            if mid == 1 and cur<=threshold:
                return 1
            if cur<=threshold and prev>threshold:
                return mid
            elif cur>threshold:
                low = mid+1
            elif prev<=threshold:
                high = mid-1
        return (low+high)//2

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def feasible(val):
            total = 0
            for i in nums:
                total += (i-1)//val + 1
            return total <= threshold
        
        left,right = 1, max(nums)
        while left < right:
            mid = left + (right-left)//2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        r = max(nums)
        l = 1
        
        def calc(div):
            s = sum([ceil(num / div) for num in nums])
            return s <= threshold
        
        while l < r:
            mid = (l + r) // 2
            val = calc(mid)
            # print (\"[%d, %d] => %d v %r\" %(l, r, mid, val))
            
            if calc(mid):
                r = mid
            else:
                l = mid + 1
        
        return l
                
        


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        s = sum(nums)
        l = len(nums)
        L = max((s + threshold - 1) // threshold, 1) - 1
        # worst case: every num is just one more of multiple of answer
        t_ = max(threshold - l, 1)
        U = (s + t_ - 1) // t_
        while L + 1 < U:
            m = (L + U) // 2
            if sum((x + m - 1) // m for x in nums) <= threshold:
                U = m
            else:
                L = m
        return U


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        def feasible(target):
            total = sum([math.ceil(num/target) for num in nums] )
            return total <= threshold
        low,high=1,sum(nums)
        while low < high:
            mid = low+(high-low)//2
            if feasible(mid):
                high = mid
            else:
                low = mid+1
        return low
            


import math
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        def isDiv(mid):
            s=0
            for i in nums:
                s+=math.ceil(i/mid)
            # print(\"Sum\",s,mid)
            return s<=threshold
            
    
        def binsearch():
            low=1
            high=sum(nums)
            while low<high:
                mid=low+(high-low)//2
                if isDiv(mid):
                    high=mid
                else:
                    low=mid+1
            return low
        return binsearch()

import math

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        if not nums:
            return sys.maxsize
        left, right = 1, 2
        while right < sys.maxsize and self.get_sum(nums, right) > threshold:
            left, right = right, right * 2

        
        while left + 1 < right:
            mid = (left + right) // 2
            if self.get_sum(nums, mid) <= threshold:
                right = mid
            else:
                left = mid
        if self.get_sum(nums, left) <= threshold:
            return left
        return right
    
    def get_sum(self, nums: List[int], divisor: int) -> int:
        result = 0
        for num in nums:
            result += math.ceil(num / divisor)
        return int(result)

from math import ceil
def is_fine(nums,val,threshold):
    tot = 0
    for i in nums:
        tot += ceil(i/val)
    if tot <= threshold:
        return True
    else:
        return False
def bSearch(l,r,nums,threshold):
    if l <= r:
        mid = (l+r)//2
        high_val = is_fine(nums,mid,threshold)
        low_val = is_fine(nums,mid-1,threshold)
        if high_val is True and low_val is False:
            return mid
        elif high_val is False and low_val is False:
            return bSearch(mid+1,r,nums,threshold)
        else:
            return bSearch(l,mid-1,nums,threshold)
    else:
        return None
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        if sum(nums) <= threshold:
            return 1
        return bSearch(2,10**6,nums,threshold)
        


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        
        def calc(nums, divisor):
            s = 0
            for num in nums:
                if num % divisor == 0:
                    s += num // divisor
                else:
                    s += num // divisor + 1
            
            # print(divisor, s)
            return s
        
        left = 1
        right = sum(nums) // (threshold-1) + threshold*100
        print((left, right))
        
        while left < right:
            mid = (left+right) // 2
            
            cur_res = calc(nums, mid)
            if cur_res > threshold:
                left = mid + 1
            else:
                right = mid
        
        return left
                


class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        end = 1
        start = end
        def findSum(div):
            return sum([math.ceil(n / div) for n in nums])
        while True:
            if findSum(end) > threshold:
                start = end
                end *= 2
            else:
                break
        while end > start:
            mid = (start + end) // 2
            # print(start, end, mid, findSum(mid))
            if findSum(mid) > threshold:
                start = mid + 1
            else:
                end = mid
        return end