How to regroup into two arrays with equal sum?

Aaron Li 0
Viewed 38

I encountered a question that I couldn't solve during my algorithm interview. The question goes:

Given an array of length n, where n is an even number, regroup the elements in the array into two smaller arrays, each with equal length (n/2), with the condition that the sum of each of these smaller arrays is equal. If this cannot be achieved, return -1.

Eg. Input: [1,1,1,2,3,3,3,6] Output: [[1,1,2,6], [1,3,3,3]]
Eg. Input: [1,4,5,6] Output: -1

I was thinking about randomly initializing two subarrays and then interchanging two elements so that their difference is at least half the total differences in the sum of two arrays. However, I had trouble coming up with a criterion that would dictate the scenario when the input is illegitimate, and the answer should be -1.

Thanks for any help and hints!

sum list dynamic-programming arrays algorithm
2 Answers

OK, I will just post my dumb solution here. I work out all the possible subsequences with sum equal to half of the total sum. Then, check if there is any subsequence with length equal to half of the length of the array.

If anyone comes up with a faster solution, please let me know :)

from collections import Counter

def partition(nums):
    if sum(nums) % 2 != 0:  # if the sum is an odd number it's impossible
        return -1
    nums.sort()
    target = sum(nums) / 2
    out = []

    ct = Counter(nums)

    def dp(cand):  # first find out all the sub-sequence with sum equal to n/2
        if sum(cand) == target:
            out.append(cand)
        remain = target - sum(cand)
        for i, number in enumerate(nums):
            if number > remain:
                break
            if (cand and number < cand[-1]) or ct[number] == 0:
                continue
            if i >= 1 and nums[i - 1] == nums[i]:
                continue
            ct[number] -= 1
            dp([*cand, number])
            ct[number] += 1

    dp([])
    for sub_array in out:
        if len(sub_array) != len(nums) / 2:
            continue  # check if there is any subsequence with exactly half length
        another_array = []
        stats = Counter(sub_array)
        for num, count in ct.items():
            another_array += [num] * (count - stats[num])
        return [another_array, sub_array]
    return -1
Aaron Li0 
 let sum=0;
 for (int i=0;i<x.length;i++)
  {sum=sum+i}
 if (sum%2!=0){
    return - 1;}
 else {
    //do your code here //
 }

If the sum of the array doesn't sum up to even number, return - 1. Hope this address your question

esoteric elf0
Related