aboutsummaryrefslogtreecommitdiff
path: root/partition_arr_min_sum_diff.py
diff options
context:
space:
mode:
Diffstat (limited to 'partition_arr_min_sum_diff.py')
-rw-r--r--partition_arr_min_sum_diff.py56
1 files changed, 56 insertions, 0 deletions
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]))