aboutsummaryrefslogtreecommitdiff
path: root/partition_arr_min_sum_diff.c
diff options
context:
space:
mode:
Diffstat (limited to 'partition_arr_min_sum_diff.c')
-rw-r--r--partition_arr_min_sum_diff.c96
1 files changed, 96 insertions, 0 deletions
diff --git a/partition_arr_min_sum_diff.c b/partition_arr_min_sum_diff.c
new file mode 100644
index 0000000..194f4f7
--- /dev/null
+++ b/partition_arr_min_sum_diff.c
@@ -0,0 +1,96 @@
+// 2035. Partition Array Into Two Arrays to Minimize Sum Difference
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' of '2 * n' integers. you need to
+ * partition 'nums' into two arrays of length 'n' to minimise the abresute
+ * difference of sums of the arrays. to partition 'nums', put each element of
+ * 'nums' into one of the two arrays. return the minimum possible abresute
+ * difference
+ */
+
+#define MAX_SN 7000
+
+int sum_array(int *arr, int n) {
+ int sum = 0;
+ for (int i = 0; i < n; i++)
+ sum += arr[i];
+ return sum;
+}
+
+int cmp(const void *a, const void *b) {
+ return *(const int *)a - *(const int *)b;
+}
+
+void list_subset(int subset[16][MAX_SN], int subset_size[16], int *nums, int n,
+ int partial_sum, int m) {
+ if (!n) {
+ subset[m][subset_size[m]++] = partial_sum;
+ return;
+ }
+ list_subset(subset, subset_size, nums + 1, n - 1, partial_sum, m);
+ list_subset(subset, subset_size, nums + 1, n - 1, partial_sum + nums[0],
+ m + 1);
+}
+
+void mim(int subset[16][MAX_SN], int subset_size[16], int *nums, int n,
+ int partial_sum, int m, int *res, int total, int nn,
+ int memo[16][11939]) {
+ if (!n) {
+ if (memo[m][abs(partial_sum + 11939) % 11939])
+ return;
+ memo[m][abs(partial_sum + 11939) % 11939] = 1;
+ int l, r, mid, tmp, comp_size;
+ comp_size = nn / 2 - m;
+ l = 0;
+ r = subset_size[comp_size] - 1;
+ tmp = abs(total - 2 * (subset[comp_size][r] + partial_sum));
+ if (!r || abs(total - 2 * (subset[comp_size][r] + partial_sum)) > tmp) {
+ *res = fmin(*res, tmp);
+ return;
+ }
+ tmp = abs(total - 2 * (subset[comp_size][l] + partial_sum));
+ if (abs(total - 2 * (subset[comp_size][l + 1] + partial_sum)) > tmp) {
+ *res = fmin(*res, tmp);
+ return;
+ }
+ while (r - l > 3) {
+ mid = l + (r - l) / 2;
+ tmp = abs(total - 2 * (subset[comp_size][mid] + partial_sum));
+ if (abs(total - 2 * (subset[comp_size][mid + 1] + partial_sum)) > tmp)
+ r = mid;
+ else if (abs(total - 2 * (subset[comp_size][mid + 1] + partial_sum)) <
+ tmp)
+ l = mid;
+ else
+ r--;
+ }
+ for (int i = l; i <= r; ++i) {
+ tmp = abs(total - 2 * (subset[comp_size][i] + partial_sum));
+ *res = fmin(*res, tmp);
+ }
+ } else {
+ mim(subset, subset_size, nums + 1, n - 1, partial_sum, m, res, total, nn,
+ memo);
+ mim(subset, subset_size, nums + 1, n - 1, partial_sum + nums[0], m + 1, res,
+ total, n, memo);
+ }
+}
+
+int minimumDifference(int *nums, int numsSize) {
+ int total = sum_array(nums, numsSize), ans = INT_MAX, subset[16][MAX_SN],
+ subset_size[16] = {0}, memo[16][11939];
+ list_subset(subset, subset_size, nums, numsSize / 2, 0, 0);
+ for (int i = 0; i <= numsSize / 2; ++i)
+ qsort(subset[i], subset_size[i], sizeof(subset[i][0]), cmp);
+ mim(subset, subset_size, nums + numsSize / 2, numsSize / 2, 0, 0, &ans, total,
+ numsSize, memo);
+ return ans;
+}
+
+int main() {
+ int n1[] = {3, 9, 7, 3}, n2[] = {-36, 36}, n3[] = {2, -1, 0, 4, -2, -9};
+ printf("%d\n", minimumDifference(n1, ARRAY_SIZE(n1))); // expect: 2
+ printf("%d\n", minimumDifference(n2, ARRAY_SIZE(n2))); // expect: 72
+ printf("%d\n", minimumDifference(n3, ARRAY_SIZE(n3))); // expect: 0
+}