diff options
Diffstat (limited to 'partition_arr_min_sum_diff.py')
-rw-r--r-- | partition_arr_min_sum_diff.py | 56 |
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])) |