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: Divide the numbers 1,2,…,n into two sets of equal sum. - Mathematics Stack Exchange
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
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
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
why not
their sum is even
eg n=3
1+2+3 = 6
so two sets can be made each having sum as 3
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
}
Nice… I’d love to hear some tips from you, how to get good at all this? How did you get so good?
I know about this approach right.
Approch I gave is helpful in cases when we have some modifications of this question.
For example
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.