aboutsummaryrefslogtreecommitdiff
path: root/find_smallest_divisor_threshold.py
diff options
context:
space:
mode:
Diffstat (limited to 'find_smallest_divisor_threshold.py')
-rw-r--r--find_smallest_divisor_threshold.py33
1 files changed, 33 insertions, 0 deletions
diff --git a/find_smallest_divisor_threshold.py b/find_smallest_divisor_threshold.py
new file mode 100644
index 0000000..ad24b38
--- /dev/null
+++ b/find_smallest_divisor_threshold.py
@@ -0,0 +1,33 @@
+# 1283. Find the Smallest Divisor Given a Threshold
+
+"""
+given an array of integers 'nums' and an integer 'threshold', we will choose
+a positive integer 'divisor', divide all the array by it and sum the
+divisions result. find the smallest divisor such that the result mentioned
+above is less than or equal to 'threshold'. each result of the division is
+rounded to the nearest integer greater than or equal to that element. the
+test cases are generated so that there will be an answer
+"""
+
+
+class Solution(object):
+ def smallestDivisor(self, nums, threshold):
+ """
+ :type nums: List[int]
+ :type threshold: int
+ :rtype: int
+ """
+ l, r = 1, max(nums)
+ while l < r:
+ m = (l + r) / 2
+ if sum((i + m - 1) / m for i in nums) > threshold:
+ l = m + 1
+ else:
+ r = m
+ return l
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.smallestDivisor(nums=[1, 2, 5, 9], threshold=6))
+ print(obj.smallestDivisor(nums=[44, 22, 33, 11, 1], threshold=5))