From c925f1740cfe00cea69b6e091dcb38d114887ad3 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Wed, 12 Feb 2025 21:41:13 -0700 Subject: 3066. minimum operations to exceed threshold value 2 --- min_ops_exceed_threshold2.c | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) create mode 100644 min_ops_exceed_threshold2.c (limited to 'min_ops_exceed_threshold2.c') 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 +} -- cgit v1.2.3