How to Divide the numbers 1,2,…,n into two sets of equal sum.

eg n=7

then answer would be

4

1 2 4 7 = sum is 14

3

3 5 6 = sum is 14

for 5, not possible.

Solution with complete proof: https://math.stackexchange.com/a/3266612/683026

How to Divide the numbers 1,2,…,n into two sets of equal sum.

eg n=7

then answer would be

4

1 2 4 7 = sum is 14

3

3 5 6 = sum is 14

for 5, not possible.

Solution with complete proof: https://math.stackexchange.com/a/3266612/683026

if the numbers are not in proper seq

maintain two arrays with prefix sum and postfix sum then see where they hav equal values

if num are like what u wrote i.e 1 to n with diff of 1 then u use Sn formula of AP to see where the exact half value can be obtained

No, you misunderstood I think. It is not always possible to do it with Sn formula, take 5 for eg:

1,2,3,4,5 you can’t divide this.

eg n=7

then answer would be

4

1 2 4 7 = sum is 14

3

3 5 6 = sum is 14

Check if it’s possible or not using sigma n formula i.e. if n*(n+1)%4==0 or not

If possible then :

If n%2==0 then answer is

1 2 3 4 5 6 7 8

first n/4 and last n/4 in one set and rest in another set

else if n%2 == 1

Remove 1,2,3 from list.

And

Set 1= 1 2

Set 2 = 3

Then remaining elements will be

4 5 6 7

Use same logic as n%2==0 that is first n/4 and last n/4 in same set and rest in other set.

It is guaranteed that n will be divisible by 4 wherever I mentioned n/4

1 Like

okk yeah i misunderstood

i thought u need contiguous array

so what u can do is take half of sum then form elements summing up to it

eg

n=7

elements are

1 2 3 4 5 6 7

sum of them is 28

so each grp must hav sum exactly 14

just choose elements frm list whose sum is 14

one way is to traverse frm largest to smallest num

one grp will hav 7+6+1 and other will hav rest

if sum is odd in case of n=5 then its not possible

2 Likes

Perfect… How did you come to this conclusion?

if u mean by %4 wala part then its simple inference

sum of n ele = n/2(2a+(n-1)d)

a=1, d=1 then

Sn = n(n+1)/2

this sum shld be divisible by 2 as i said in my post

hence Sn/2 shld be an int

Sn/2 = n(n+1)/4 shld be int

hence he checked if n(n+1) is divisible by 4 or not

However abt the last part i.e segregating elements into two sets, i feel like my way is much simple

Got the %4 wala part.

I didn’t get how It worked for odd n.

There are just two cases when it is possible.

N%4=0 and N%4=3

So when N%4=0 then

In 1 2 3 4 5 6 7 8

1+8= 2+7 = 3+6 …

For n%4=3

Remove 3 elements and it becomes similar as N%4=0

Now 123 can be divided into two sets easily.

So this is how I thought about it

3 Likes

why not

their sum is even

eg n=3

1+2+3 = 6

so two sets can be made each having sum as 3

1 Like

another simple way of segregating elements into sets :-

for n=8 we know that each set must hav sum as 18

let req=18

so

traverse frm largest to smallest ele{

add to our set if its>=req

req-=ele

if req==0 break

}

1 Like

Nice… I’d love to hear some tips from you, how to get good at all this? How did you get so good?

1 Like

I know about this approach right.

Approch I gave is helpful in cases when we have some modifications of this question.

For example

www.codechef.com/problems/PRTITION

1 Like

What I did was participate in every contest without even missing one contest.

Since November lunchtime 2017.

That’s it.

Google when you are stuck.

4 Likes