aboutsummaryrefslogtreecommitdiff
path: root/reduce_array_size_half.c
diff options
context:
space:
mode:
Diffstat (limited to 'reduce_array_size_half.c')
-rw-r--r--reduce_array_size_half.c38
1 files changed, 38 insertions, 0 deletions
diff --git a/reduce_array_size_half.c b/reduce_array_size_half.c
new file mode 100644
index 0000000..da62032
--- /dev/null
+++ b/reduce_array_size_half.c
@@ -0,0 +1,38 @@
+// 1338. Reduce Array Size to The Half
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'arr'. you can choose a set of integers and
+ * remove all the occurences of these integers in the array. return the minimum
+ * size of the set so that at least half of the integers in the array are
+ * removed.
+ */
+
+int minSetSize(int *arr, int arrSize) {
+ int *hash = (int *)calloc(100001, sizeof(int));
+ int *hash_cnt = (int *)calloc(arrSize + 1, sizeof(int));
+ int max = 0, ans = 0, ans_cnt = 0;
+ for (int i = 0; i < arrSize; i++) {
+ if (hash[arr[i]])
+ hash_cnt[hash[arr[i]]]--;
+ hash_cnt[++hash[arr[i]]]++;
+ if (hash[arr[i]] > max)
+ max = hash[arr[i]];
+ }
+ while (ans_cnt < arrSize / 2) {
+ while (!hash_cnt[max])
+ max--;
+ while (ans_cnt < arrSize / 2 && hash_cnt[max]) {
+ ans_cnt += max;
+ hash_cnt[max]--;
+ ans++;
+ }
+ }
+ return ans;
+}
+
+int main() {
+ int a1[] = {3, 3, 3, 3, 5, 5, 5, 2, 2, 7}, a2[] = {7, 7, 7, 7, 7, 7};
+ printf("%d\n", minSetSize(a1, ARRAY_SIZE(a1))); // expect: 2
+ printf("%d\n", minSetSize(a2, ARRAY_SIZE(a2))); // expect: 1
+}