aboutsummaryrefslogtreecommitdiff
path: root/least_num_unique_int.c
diff options
context:
space:
mode:
Diffstat (limited to 'least_num_unique_int.c')
-rw-r--r--least_num_unique_int.c41
1 files changed, 41 insertions, 0 deletions
diff --git a/least_num_unique_int.c b/least_num_unique_int.c
new file mode 100644
index 0000000..4e4b4f6
--- /dev/null
+++ b/least_num_unique_int.c
@@ -0,0 +1,41 @@
+// 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
+}