Create find-the-smallest-divisor-given-a-threshold.py

yingl · web-flow · commit 6d9ebd666630 · 2022-02-11T22:50:59.000+08:00
diff --git a/find-the-smallest-divisor-given-a-threshold.py b/find-the-smallest-divisor-given-a-threshold.py
@@ -0,0 +1,31 @@
+import math
+
+class Solution:
+    """
+    @param nums: an array of integers
+    @param threshold: an integer
+    @return: return the smallest divisor
+    """
+    def smallestDivisor(self, nums, threshold):
+        # write your code here
+        ret = 0
+        min_value = sum(nums)
+        l, r = 1, max(nums)
+        while l <= r:
+            mid = int((l + r) / 2)
+            if self.check(nums, mid, threshold):
+                r = mid - 1
+                ret = mid
+            else:
+                l = mid + 1
+        return ret
+
+    def check(self, nums, div, threshold):
+        s = 0
+        for i in nums:
+            s += math.ceil(i / div)
+            if s > threshold:
+                return False
+        return True
+      
+# medium: https://www.lintcode.com/problem/1816/
