aboutsummaryrefslogtreecommitdiff
path: root/min_ops_exceed_threshold2.c
diff options
context:
space:
mode:
Diffstat (limited to 'min_ops_exceed_threshold2.c')
-rw-r--r--min_ops_exceed_threshold2.c36
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
+}