diff options
-rw-r--r-- | find_smallest_divisor_threshold.c | 40 | ||||
-rw-r--r-- | find_smallest_divisor_threshold.py | 33 |
2 files changed, 73 insertions, 0 deletions
diff --git a/find_smallest_divisor_threshold.c b/find_smallest_divisor_threshold.c new file mode 100644 index 0000000..ad0a0f5 --- /dev/null +++ b/find_smallest_divisor_threshold.c @@ -0,0 +1,40 @@ +// 1283. Find the Smallest Divisor Given a Threshold +#include "leetcode.h" + +/* + * 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 + */ + +int divide(int *nums, int numsSize, double k) { + int res = 0; + for (int i = 0; i < numsSize; i++) + res += ceil(nums[i] / k); + return res; +} + +int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } + +int smallestDivisor(int *nums, int numsSize, int threshold) { + qsort(nums, numsSize, sizeof(int), cmp); + int left = 1, right = 1000000, mid; + while (left < right) { + mid = (left + right) / 2; + if (divide(nums, numsSize, mid) <= threshold) + right = mid; + else + left = mid + 1; + } + mid = (left + right) / 2; + return mid; +} + +int main() { + int n1[] = {1, 2, 5, 9}, n2[] = {44, 22, 33, 11, 1}; + printf("%d\n", smallestDivisor(n1, ARRAY_SIZE(n1), 6)); // expect: 5 + printf("%d\n", smallestDivisor(n2, ARRAY_SIZE(n2), 5)); // expect: 44 +} 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)) |