diff options
-rw-r--r-- | partition_arr_min_sum_diff.c | 96 | ||||
-rw-r--r-- | partition_arr_min_sum_diff.py | 56 |
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])) |