diff options
Diffstat (limited to 'find_smallest_divisor_threshold.c')
-rw-r--r-- | find_smallest_divisor_threshold.c | 40 |
1 files changed, 40 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 +} |