aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--partition_arr_min_sum_diff.c96
-rw-r--r--partition_arr_min_sum_diff.py56
2 files changed, 152 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
+}
diff --git a/partition_arr_min_sum_diff.py b/partition_arr_min_sum_diff.py
new file mode 100644
index 0000000..6a89257
--- /dev/null
+++ b/partition_arr_min_sum_diff.py
@@ -0,0 +1,56 @@
+# 2035. Partition Array Into Two Arrays to Minimize Sum Difference
+from bisect import bisect_left
+from itertools import combinations
+
+"""
+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
+"""
+
+
+class Solution(object):
+ def minimumDifference(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ n = len(nums)
+
+ def get_sums(nums):
+ res = {}
+ for k in range(1, n + 1):
+ sums = []
+ for c in combinations(nums, k):
+ s = sum(c)
+ sums.append(s)
+ res[k] = sums
+ return res
+
+ left_part, right_part = nums[:n], nums[n:]
+ left_sums, right_sums = get_sums(left_part), get_sums(right_part)
+ ans = abs(sum(left_part) - sum(right_part))
+ total = sum(nums)
+ half = total // 2
+ for i in range(1, n):
+ left, right = left_sums[i], right_sums[n - i]
+ right.sort()
+ for j in left:
+ r = half - j
+ p = bisect_left(right, r)
+ for k in [p, p - 1]:
+ if 0 <= k < len(right):
+ left_ans_sum = j + right[k]
+ right_ans_sum = total - left_ans_sum
+ diff = abs(left_ans_sum - right_ans_sum)
+ ans = min(ans, diff)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minimumDifference(nums=[3, 9, 7, 3]))
+ print(obj.minimumDifference(nums=[-36, 36]))
+ print(obj.minimumDifference(nums=[2, -1, 0, 4, -2, -9]))