aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-08-02 07:11:12 +0100
committerJack Sangdahl <[email protected]>2025-08-02 07:11:12 +0100
commit0025b8254ac7fd37f1c82686f3cb728e1ef2e1fe (patch)
tree45a4a80e484a62d025dc8fc2531dc6dffb3369c0
parent0434a2a41dfb2a3b17f785cb07de16c5b09b0d56 (diff)
downloadleetcode-0025b8254ac7fd37f1c82686f3cb728e1ef2e1fe.tar.gz
leetcode-0025b8254ac7fd37f1c82686f3cb728e1ef2e1fe.zip
2561. rearranging fruits
-rw-r--r--rearranging_fruits.c104
-rw-r--r--rearranging_fruits.py39
2 files changed, 143 insertions, 0 deletions
diff --git a/rearranging_fruits.c b/rearranging_fruits.c
new file mode 100644
index 0000000..4252d05
--- /dev/null
+++ b/rearranging_fruits.c
@@ -0,0 +1,104 @@
+// 2561. Rearranging Fruits
+#include "leetcode.h"
+
+/*
+ * you have two fruit baskests containing 'n' fruits each. you are given two
+ * indexed integer arrays 'basket1' and 'basket2' representing the cost of fruit
+ * in each baset. you want o make both baskets equal. to do so, you can use the
+ * following operation as many times as you want: chose two indices 'i' and 'j'
+ * and swap the i'th fruit of 'basket1' with the j'th fruit of 'basket2'. the
+ * cost of the swap is 'min(basket1[i], basket2[j])'. two baskets are considered
+ * equal if sorting them according to the fruit cost makes them exactly the same
+ * baksets. return the minimum cost to make both baskets equal or -1 if
+ * impossible.
+ */
+
+struct map_entry {
+ int key;
+ int val;
+};
+
+struct map {
+ struct map_entry *entries;
+ int size;
+ int capacity;
+};
+
+void map_init(struct map *obj) {
+ obj->capacity = 16;
+ obj->size = 0;
+ obj->entries =
+ (struct map_entry *)malloc(obj->capacity * sizeof(struct map_entry));
+}
+
+void map_insert(struct map *obj, int key, int delta) {
+ for (int i = 0; i < obj->size; i++)
+ if (obj->entries[i].key == key) {
+ obj->entries[i].val += delta;
+ return;
+ }
+ if (obj->size == obj->capacity) {
+ obj->capacity *= 2;
+ obj->entries = (struct map_entry *)realloc(
+ obj->entries, obj->capacity * sizeof(struct map_entry));
+ }
+ obj->entries[obj->size].key = key;
+ obj->entries[obj->size].val = delta;
+ obj->size++;
+}
+
+int cmp(const void *a, const void *b) {
+ struct map_entry *aa = (struct map_entry *)a;
+ struct map_entry *bb = (struct map_entry *)b;
+ return aa->key - bb->key;
+}
+
+void map_sort(struct map *obj) {
+ qsort(obj->entries, obj->size, sizeof(struct map_entry), cmp);
+}
+
+long long minCost(int *basket1, int basket1Size, int *basket2,
+ int basket2Size) {
+ long long ans = 0;
+ struct map map;
+ map_init(&map);
+ for (int i = 0; i < basket1Size; i++) {
+ map_insert(&map, basket1[i], 1);
+ map_insert(&map, basket2[i], -1);
+ }
+ map_sort(&map);
+ if (!map.size)
+ return 0;
+ int m = map.entries[0].key;
+ int *arr = NULL, arr_size = 0, arr_capacity = 0;
+ for (int i = 0; i < map.size; i++) {
+ int val = map.entries[i].key, key = map.entries[i].val;
+ if (key % 2) {
+ free(map.entries);
+ if (arr)
+ free(arr);
+ return -1;
+ }
+ int cnt = abs(key) / 2;
+ for (int j = 0; j < cnt; j++) {
+ if (arr_size == arr_capacity) {
+ arr_capacity = !arr_capacity ? 1 : arr_capacity * 2;
+ arr = (int *)realloc(arr, arr_capacity * sizeof(int));
+ }
+ arr[arr_size++] = val;
+ }
+ }
+ for (int i = 0; i < arr_size / 2; i++)
+ ans += (arr[i] < 2 * m) ? arr[i] : 2 * m;
+ free(map.entries), free(arr);
+ return ans;
+}
+
+int main() {
+ int b11[] = {4, 2, 2, 2}, b21[] = {1, 4, 1, 2};
+ int b12[] = {2, 3, 4, 1}, b22[] = {3, 2, 5, 1};
+ printf("%lld\n",
+ minCost(b11, ARRAY_SIZE(b11), b21, ARRAY_SIZE(b21))); // expect: 1
+ printf("%lld\n",
+ minCost(b12, ARRAY_SIZE(b12), b22, ARRAY_SIZE(b22))); // expect: -1
+}
diff --git a/rearranging_fruits.py b/rearranging_fruits.py
new file mode 100644
index 0000000..7040731
--- /dev/null
+++ b/rearranging_fruits.py
@@ -0,0 +1,39 @@
+# 2561. Rearranging Fruits
+from collections import Counter
+
+"""
+you have two fruit baskests containing 'n' fruits each. you are given two
+indexed integer arrays 'basket1' and 'basket2' representing the cost of fruit
+in each baset. you want o make both baskets equal. to do so, you can use the
+following operation as many times as you want: chose two indices 'i' and 'j'
+and swap the i'th fruit of 'basket1' with the j'th fruit of 'basket2'. the
+cost of the swap is 'min(basket1[i], basket2[j])'. two baskets are considered
+equal if sorting them according to the fruit cost makes them exactly the same
+baksets. return the minimum cost to make both baskets equal or -1 if
+impossible.
+"""
+
+
+class Solution(object):
+ def minCost(self, basket1, basket2):
+ """
+ :type basket1: List[int]
+ :type basket2: List[int]
+ :rtype: int
+ """
+ cnt = Counter(basket1 + basket2)
+ for i in cnt:
+ if cnt[i] % 2:
+ return -1
+ cnt[i] >>= 1
+ a1 = list((Counter(basket1) - cnt).elements())
+ a2 = list((Counter(basket2) - cnt).elements())
+ low = min(cnt)
+ c = sorted(a1 + a2)
+ return sum(min(low * 2, c[i]) for i in range(len(a1)))
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minCost(basket1=[4, 2, 2, 2], basket2=[1, 4, 1, 2]))
+ print(obj.minCost(basket1=[2, 3, 4, 1], basket2=[3, 2, 5, 1]))