Algorithm to divide array of length n containing numbers from 1 to n (no repetition) into two equal sum

0
votes

You are giving array of length N and numbers in the array contain 1 to N no repetition. You need to check if the array can be divided into to list of equal sum.

I know it can be solved using subset sum problem whose time complexity is. Is there an algorithm so that I can reduce the time complexity?

2
arraysalgorithm
you do one thing sum all the elements of the array and then divide it by 2 if there is no non 0 value then it is possible to break the array – smn_onrocks
does the lists need to be continuous ? i mean are you looking fro sub-arrays or subsequences ? – Méhdi Màick
List don't need to be continuous so basically subsequence – Suresh Arora

2 Answers

2
votes

As per your requirements, we conclude the array will always contain numbers 1 to N. So if Array.Sum()==Even the answer is YES, otherwise NO.

0
votes

Since the sum of elements from 1 to n equals n*(n+1)/2, you have to check if n*(n+1) is a multiple of 4, which is equivalent to checking if n is a multiple of 4, or if n+1 is a multiple of 4. The complexity of it is O(1). If this condition is met, the two subsets are :

if n is a multiple of 4: sum up the odd numbers of first half with even numbers of second half on one hand, and even numbers of first half with odd of second half on the other. For instance, 1 3 5 8 10 12 , and 2 4 6 7 9 11.

if n = 3 modulo 4 : almost the same thing, just split the first 3 between 1 and 2 on one hand, 3 on the other, you have a remaining serie which has a size multiple of 4. For instance : 1 2 4 7 , and 3 5 6 ; or if you prefer, 3 4 7, and 1 2 5 6.