aboutsummaryrefslogtreecommitdiff
path: root/min_ops_exceed_threshold2.c
blob: 0b7f56adef3de36111891517bd0eb7ab6d11db50 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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
}