leetcode

// 1481. Least Number of Unique Integers after K Removals
#include "leetcode.h"

/*
 * given an array of integers 'arr' and an integer 'k', find the least number of
 * unique integers after removing exactly 'k' elements.
 */

int cmp(const void *a, const void *b) {
  return *(const int *)a > *(const int *)b;
}

int findLeastNumOfUniqueInts(int *arr, int arr_size, int k) {
  qsort(arr, arr_size, sizeof(int), cmp);
  int idx = 0, cnt = 0, ans = 0;
  int *tmp = (int *)malloc(arr_size * sizeof(int));
  for (int i = 0; i < arr_size; i++) {
    int j = i;
    while (j < arr_size && arr[j] == arr[i])
      cnt++, j++;
    tmp[idx++] = cnt;
    i = j - 1;
    cnt = 0;
  }
  qsort(tmp, idx, sizeof(int), cmp);
  for (int i = 0; i < idx; i++) {
    ans += tmp[i];
    if (ans >= k) {
      ans = (ans == k) ? idx - i - 1 : idx - i;
      break;
    }
  }
  free(tmp);
  return ans;
}

int main() {
  int a1[] = {5, 5, 4}, a2[] = {4, 3, 1, 1, 3, 3, 2};
  printf("%d\n", findLeastNumOfUniqueInts(a1, ARRAY_SIZE(a1), 1)); // expect: 1
  printf("%d\n", findLeastNumOfUniqueInts(a2, ARRAY_SIZE(a2), 3)); // expect: 2
}