You are given an array of integers nums and an integer K, your task is to find the smallest positive integer divisor, such that upon dividing all the elements of the given array by it, the sum of the division's result is less than or equal to the given integer K.
Each result of the division is rounded to the nearest integer greater than or equal to that element. For Example: 7/3 = 3.
Example:
Input: 
A = [1 2 5 9]
6
Output:
5
Explanation:
If the divisor is 5 the sum will be 5 (1+1+1+2), which is less than 6.
Your Task:
Complete the function int smallestDivisor(), which takes a vector nums and an integer K and returns the smallest integer as asked.
Expected Time Complexity: O(nlogn).
Expected Auxiliary Space: O(n).
Constraints:
1 <= nums.length <= 5 * 10^{5}
1 <= nums[i] <= 10^{9}
nums.length <= K <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3

class Solution:

    def smallestDivisor(self, nums, K):

        # Code here

Solutions:
import math

class Solution:

	def smallestDivisor(self, nums, K):
		left = 1
		right = max(nums)
		while left <= right:
			mid = (left + right) // 2
			summ = 0
			for num in nums:
				summ += (num + mid - 1) // mid
			if summ > K:
				left = mid + 1
			else:
				right = mid - 1
		return left


class Solution:

	def ok(self, nums, k, mi):
		return sum(((a + mi - 1) // mi for a in nums)) <= k

	def smallestDivisor(self, nums, K):
		(lo, hi) = (1, max(nums))
		ans = 0
		while lo <= hi:
			mi = (lo + hi) // 2
			if self.ok(nums, K, mi):
				ans = mi
				hi = mi - 1
			else:
				lo = mi + 1
		return ans


class Solution:

	def smallestDivisor(self, nums, K):

		def calculate_sum(divisor):
			return sum([(num - 1) // divisor + 1 for num in nums])
		(left, right) = (1, max(nums))
		while left <= right:
			mid = (left + right) // 2
			if calculate_sum(mid) <= K:
				right = mid - 1
			else:
				left = mid + 1
		return left


import math

class Solution:

	def divsum(self, arr, val):
		sumval = 0
		for ele in arr:
			sumval += ele // val + (1 if ele % val != 0 else 0)
		return sumval

	def smallestDivisor(self, nums, K):
		(low, high) = (1, max(nums))
		minint = high
		while low <= high:
			mid = (low + high) // 2
			sumdiv = self.divsum(nums, mid)
			if sumdiv <= K:
				minint = mid
				high = mid - 1
			else:
				low = mid + 1
		return minint


class Solution:

	def smallestDivisor(self, nums, threshold):
		low = 1
		ans = float('inf')
		high = max(nums)
		while low <= high:
			mid = low + high >> 1
			sumation = 0
			for num in nums:
				if num % mid == 0:
					sumation += num // mid
				else:
					sumation += num // mid + 1
			if sumation > threshold:
				low = mid + 1
			else:
				ans = min(ans, mid)
				high = mid - 1
		return ans


class Solution:

	def smallestDivisor(self, nums, K):
		threshold = K
		lo = 1
		hi = max(nums)
		ans = 0

		def possible(mid):
			res = 0
			for num in nums:
				res += num // mid + (1 if num % mid else 0)
			if res <= threshold:
				return True
			return False
		while lo <= hi:
			mid = (lo + hi) // 2
			if possible(mid):
				ans = mid
				hi = mid - 1
			else:
				lo = mid + 1
		return ans


from math import ceil

class Solution:

	def getRoundedSum(self, nums, div):
		if div == 0:
			return float('inf')
		sum = 0
		for elem in nums:
			sum += ceil(elem / div)
		return sum

	def smallestDivisor(self, nums, k):
		if k == len(nums):
			return max(nums)
		else:
			(l, r, curr_div) = (0, max(nums), 0)
			min_div = r
			while l <= r:
				curr_div = (l + r) // 2
				rounded_sum = self.getRoundedSum(nums, curr_div)
				if rounded_sum <= k:
					r = curr_div - 1
					min_div = min(min_div, curr_div)
				else:
					l = curr_div + 1
			return min_div


class Solution:

	def smallestDivisor(self, nums, K):
		low = 1
		high = max(nums)
		while low < high:
			mid = (low + high) // 2
			s = sum(((n - 1) // mid + 1 for n in nums))
			if s <= K:
				high = mid
			else:
				low = mid + 1
		return low


import math as m

class Solution:

	def smallestDivisor(self, n, t):

		def check(n, k):
			a = 0
			for i in n:
				a += m.ceil(i / k)
			return a
		l = 1
		r = max(n)
		res = 0
		while l <= r:
			mid = (l + r) // 2
			if check(n, mid) > t:
				l = mid + 1
			else:
				res = mid
				r = mid - 1
		return res


from math import ceil

class Solution:

	def smallestDivisor(self, nums, K):

		def divide(d):
			div_sum = 0
			for i in nums:
				div_sum += ceil(i / d)
			return div_sum
		low = 1
		high = max(nums)
		res = -1
		while low <= high:
			mid = (low + high) // 2
			if divide(mid) <= K:
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res


import math

class Solution:

	def smallestDivisor(self, nums, K):

		def approve(val):
			count = 0
			for p in nums:
				count += math.ceil(p / val)
			return count
		l = 1
		r = max(nums)
		res = -1
		while l <= r:
			mid = l + (r - l) // 2
			if approve(mid) <= K:
				res = mid
				r = mid - 1
			else:
				l = mid + 1
		return res


class Solution:

	def smallestDivisor(self, nums, K):
		import math
		(left, right) = (1, max(nums))
		while left < right:
			mid = (left + right) // 2
			y = 0
			for i in nums:
				x = i / mid
				y += math.ceil(x)
			if y > K:
				left = mid + 1
			else:
				right = mid
		return left


import math

class Solution:

	def smallestDivisor(self, nums, K):
		l = 1
		r = max(nums) + 1
		while l <= r:
			mid = l + (r - l) // 2
			sum = 0
			for i in nums:
				sum = sum + math.ceil(i / mid)
			if sum <= K:
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return ans


class Solution:

	def smallestDivisor(self, nums, K):
		(l, r) = (1, max(nums))
		while l < r:
			mid = (l + r) // 2
			if sum(((i + mid - 1) // mid for i in nums)) > K:
				l = mid + 1
			else:
				r = mid
		return r


class Solution:

	def smallestDivisor(self, nums, K):
		ans = max(nums)
		low = 1
		high = ans
		while low <= high:
			mid = (low + high) // 2
			total = 0
			for val in nums:
				total += val // mid
				if val % mid != 0:
					total += 1
			if total <= K:
				ans = min(ans, mid)
				high = mid - 1
			else:
				low = mid + 1
		return ans


import math
import sys

class Solution:

	def smallestDivisor(self, nums, K):
		s = 1
		e = max(nums)
		ans = sys.maxsize
		while s <= e:
			count = 0
			m = (s + e) // 2
			for i in nums:
				count += math.ceil(i / m)
			if count == K:
				ans = min(ans, m)
				e = m - 1
			elif count < K:
				ans = min(ans, m)
				e = m - 1
			else:
				s = m + 1
		return ans


import math

class Solution:

	def smallestDivisor(self, arr, K):
		left = 1
		right = max(arr)
		ans = right
		while left <= right:
			mid = (left + right) // 2
			sum = 0
			for i in arr:
				sum += math.ceil(i / mid)
			if sum <= K:
				ans = mid
				right = mid - 1
			else:
				left = mid + 1
		return ans


import math

class Solution:

	def smallestDivisor(self, nums, K):
		low = 1
		high = max(nums)
		result = float('inf')
		while low <= high:
			mid = (low + high) // 2
			s = sum([math.ceil(i / mid) for i in nums])
			result = mid
			if s <= K:
				result = mid
				high = mid - 1
			else:
				low = mid + 1
		return low


import math

class Solution:

	def smallestDivisor(self, nums, K):
		low = 1
		high = max(nums)
		ans = float('-inf')
		while low <= high:
			mid = low + (high - low) // 2
			if self.isPossible(nums, mid, K) <= K:
				high = mid - 1
				ans = mid
			else:
				low = mid + 1
		return ans

	def isPossible(self, nums, mid, K):
		sum = 0
		div = 0
		for ele in nums:
			div = math.ceil(ele / mid)
			sum += div
		return sum


import math

class Solution:

	def smallestDivisor(self, nums, K):
		i = 1
		j = max(nums)
		while i < j:
			mid = i + j >> 1
			summ = 0
			for a in nums:
				summ += math.ceil(a / mid)
			if summ <= K:
				j = mid
			else:
				i = mid + 1
		return i


import math

class Solution:

	def check(self, mid):
		count = 0
		for d in nums:
			count += math.ceil(d / mid)
		return count

	def smallestDivisor(self, nums, K):
		start = 1
		end = max(nums) + 1
		count = 0
		if sum(nums) < K:
			return 1
		while start <= end:
			mid = start + (end - start) // 2
			if self.check(mid) <= K:
				ans = mid
				end = mid - 1
			else:
				start = mid + 1
		return ans


import math

class Solution:

	def smallestDivisor(self, nums, K):
		low = 1
		high = max(nums)
		ans = high
		while low <= high:
			mid = low + (high - low) // 2
			sum = 0
			for i in range(len(nums)):
				sum += (nums[i] + mid - 1) // mid
			if sum <= K:
				ans = min(ans, mid)
				high = mid - 1
			else:
				low = mid + 1
		return ans


import math

class Solution:

	def smallestDivisor(self, nums, K):
		l = 1
		h = max(nums)
		while l < h:
			m = (l + h) // 2
			c = 0
			for i in nums:
				c += math.ceil(i / m)
			if c > K:
				l = m + 1
			else:
				h = m
		return l


class Solution:

	def check(self, nums, thresold, mid):
		total = 0
		for i in nums:
			if i % mid == 0:
				total += i // mid
			else:
				total = total + i // mid + 1
		if total <= thresold:
			return True
		return False

	def smallestDivisor(self, nums, threshold):
		start = 1
		end = max(nums)
		ans = -1
		while start <= end:
			mid = (start + end) // 2
			if self.check(nums, threshold, mid):
				ans = mid
				end = mid - 1
			else:
				start = mid + 1
		return ans


import math

class Solution:

	def smallestDivisor(self, nums, K):
		(l, r) = (1, max(nums))
		res = -1
		while l <= r:
			mid = (l + r) // 2
			s = 0
			s = sum((math.ceil(x / mid) for x in nums))
			if s <= K:
				res = mid
				r = mid - 1
			else:
				l = mid + 1
		return res


class Solution:

	def solve(self, arr, k):
		count = 0
		for i in arr:
			if i % k == 0:
				count += i // k
			else:
				count += i // k + 1
		return count

	def smallestDivisor(self, nums, K):
		(l, h) = (1, max(nums) + 1)
		ans = 1
		while l <= h:
			mid = (l + h) // 2
			temp = self.solve(nums, mid)
			if temp <= K:
				ans = mid
				h = mid - 1
			else:
				l = mid + 1
		return ans


import math

class Solution:

	def smallestDivisor(self, nums, k):

		def divide(mid):
			return sum([math.ceil(i / mid) for i in nums]) <= k
		low = 1
		high = max(nums)
		while low <= high:
			mid = (low + high) // 2
			if divide(mid):
				high = mid - 1
			else:
				low = mid + 1
		return low


import math

class Solution:

	def smallestDivisor(self, N, t):
		N.sort()
		(a, b, ceil) = (1, N[-1], math.ceil)
		while a < b:
			m = (a + b) // 2
			if sum((ceil(n / m) for n in N)) > t:
				a = m + 1
			else:
				b = m
		return a


import math

class Solution:

	def smallestDivisor(self, nums, K):
		N = len(nums)
		(low, high) = (1, max(nums))
		while low < high:
			mid = int((low + high) // 2)
			divisorSum = self.getDivisorSum(nums, N, K, mid)
			if divisorSum <= K:
				high = mid
			else:
				low = mid + 1
		return low

	def getDivisorSum(self, nums, N, K, divisor):
		return sum(((val + divisor - 1) // divisor for val in nums))


class Solution:

	def smallestDivisor(self, nums, K):

		def sumOfQuotients(divisor):
			return sum(((val + divisor - 1) // divisor for val in nums))
		n = len(nums)
		(left, right) = (1, max(nums) + 1)
		while left <= right:
			mid = left + right >> 1
			if sumOfQuotients(mid) > K:
				left = mid + 1
			else:
				right = mid - 1
		return left