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

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Data structures

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
			if mid == maxValue:
				return maxValue
			sum1 = self.calculateSum(nums, mid)
			sum2 = self.calculateSum(nums, mid + 1)
			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):
		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)
		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:
		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:
		(low, high) = (1, max(nums))
		while low < high:
			mid = (low + high) // 2
			if sum(((i + mid - 1) // mid for i in nums)) > threshold:
				low = mid + 1
			else:
				high = mid
		return low


class Solution:

	def smallestDivisor(self, nums: List[int], threshold: int) -> int:
		(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:
			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


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:
		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:
		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])
			next_sum = sum([math.ceil(x / (mid + 1)) for x in nums])
			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:

		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 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)
			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)


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:
		l = 1
		r = max(nums)
		while l < r:
			m = l + (r - l) // 2
			s = sum([ceil(x / m) for x in nums])
			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:
		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


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


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


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


class Solution:

	def smallestDivisor(self, nums: List[int], threshold: int) -> int:
		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
			if total > threshold:
				i = m + 1
			elif total <= threshold:
				j = m - 1
				ans = m
			m = (i + j) // 2
		return ans


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 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 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:
		(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 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


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:

		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


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:
		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


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


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


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])
			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


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(1000000.0))
		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 dfs(m):
			r = 0
			for i in nums:
				r += math.ceil(i / m)
				if r > threshold:
					return False
			return True
		(l, r) = (1, int(1000000.0))
		while l <= r:
			m = (l + r) // 2
			if dfs(m):
				r = m - 1
			else:
				l = m + 1
		return l


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)
			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


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
		while i < j:
			mid = (i + j) // 2
			x = divisor(l, mid)
			if x < t:
				j = mid
			elif x == t:
				break
			else:
				i = mid + 1
			if i == j:
				mid = j
				break
		while 1:
			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 check(div):
			return threshold >= sum([elem / div if elem % div == 0 else elem // div + 1 for elem in nums])

		def bst(low, high):
			mid = (low + high) // 2
			if low > high:
				return -1
			elif low == high:
				if check(low):
					return low
				else:
					return -1
			elif 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]))


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:
			return end
		while start >= end:
			mid = (start + end) // 2
			dsum = divide_and_sum(nums, mid)
			if dsum == threshold:
				while divide_and_sum(nums, mid) == threshold:
					mid -= 1
				return mid + 1
			if dsum > threshold:
				end = mid + 1
			if dsum < threshold:
				start = mid - 1
		return end


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 ok(mid):
				hi = mid - 1
			else:
				lo = mid + 1
		return lo


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))


import math

class Solution:

	def smallestDivisor(self, nums, threshold):
		nums.sort()
		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:
		l = 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
		if self.search(nums, l, threshold) >= 0:
			return l
		else:
			return 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 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


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 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:
		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
			if mid_result > threshold:
				left = mid + 1
			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


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:
		s = sum(nums)
		l = len(nums)
		L = max((s + threshold - 1) // threshold, 1) - 1
		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)
			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()


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
			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
			if findSum(mid) > threshold:
				start = mid + 1
			else:
				end = mid
		return end