diff options
Diffstat (limited to 'min_ops_exceed_threshold2.c')
-rw-r--r-- | min_ops_exceed_threshold2.c | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/min_ops_exceed_threshold2.c b/min_ops_exceed_threshold2.c new file mode 100644 index 0000000..0b7f56a --- /dev/null +++ b/min_ops_exceed_threshold2.c @@ -0,0 +1,36 @@ +// 3066. Minimum Operations to Exceed Threshold Value II +#include "leetcode.h" + +/* + * you are given a 0-indexed integer array 'nums', and an integer 'k'. in one + * operation, you will take the two smallest integers 'x' and 'y' in 'nums', + * remove 'x' and 'y' from 'nums', and add 'min(x, y) * 2 + max(x, y)' anywhere + * in the array. note that you can only apply the described operation if 'nums' + * contains at least two elements. return the minimum number of operations + * needed so that all elements of the array are greater than or equal to 'k'. + */ + +int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } + +int minOperations(int *nums, int numsSize, int k) { + qsort(nums, numsSize, sizeof(int), cmp); + int *arr = (int *)malloc(numsSize * sizeof(int)); + for (int i = 0, j = 0, m = 0, cnt = 0, x, y;; ++cnt) { + x = i < numsSize && (j >= m || nums[i] <= arr[j]) ? nums[i++] : arr[j++]; + if (x >= k) { + free(arr); + return cnt; + } + y = i < numsSize && (j >= m || nums[i] <= arr[j]) ? nums[i++] : arr[j++]; + long tmp = 2L * x + y; + arr[m++] = tmp < k ? (int)tmp : k; + } + free(arr); + return -1; +} + +int main() { + int n1[] = {2, 11, 10, 1, 3}, n2[] = {1, 1, 2, 4, 9}; + printf("%d\n", minOperations(n1, ARRAY_SIZE(n1), 10)); // expect: 2 + printf("%d\n", minOperations(n2, ARRAY_SIZE(n2), 20)); // expect: 4 +} |