# PROBLEM LINK:

[Contest: IYWT2021 - If you win this, Bhel Puri Treat] (Contest Page | CodeChef )

*Author:* Meenaksshi S

*Tester:* Meenaksshi S

*Editorialist:* Meenaksshi S

# DIFFICULTY:

EASY

# PREREQUISITES:

Math

# PROBLEM:

Divide a sequence of n integers (1,2,3…n) into two sets X and Y such that each integer belongs to only one set (either X or Y) and sum of all integers in one set is equal to the sum of all integers in the other set i.e. ( Sum(X) = Sum(Y) )

Given the integer n, determine if it is possible to divide the sequence of n integers in such a way.

# QUICK EXPLANATION:

Calculate the sum of 1 to n integers.

Sum= \sum_{i = 1}^{N} i

Formula: \frac{n * (n+1)}{2}

If the sum is odd then it is impossible (Answer: “NO”)

Else if it is even then there is always a way to divide the sequence into two parts of equal sum. (Answer: “YES” ) → Proof is given in detail in explanation.

# EXPLANATION:

```
#include "bits/stdc++.h"
using namespace std;
int main()
{
int n;
cin >> n;
int sum = (n * (n + 1)) / 2; // formula for sum of first n natural numbers
if (sum % 2 == 0) // sum is even
cout << "YES";
else // sum is odd
cout << "NO";
return 0;
}
```

If \frac{n * (n+1)}{2} is even → Output “YES”

Otherwise → Output “NO”

Proof:

Let S = (n*(n+1)) /2

If we have an integer sequence of 1,2,3,…,n then we can obtain any number from 0 to S as the sum of some elements from this sequence.

Eg: (Greedily)

n = 3

S = (n*(n+1))/2 => (3*4)/2

=>S = 6

1 → 1

2 → 2

3 → 3

4 → 3+1

5 → 2+3

6 → 3+3

Hence if S is even, then we can obtain the sum S/2 in X.

And the remaining in Y => (S – (S/2)) = (S/2)

Hence the sum of integers in sets X and Y is equal to (S/2)

Therefore, there is always a possibility to obtain equal sum in sets X and Y if S is even. Answer is “YES”.

If S is odd it is only possible to obtain ceil(S/2) in one set and floor(S/2) in the other set. But it is never possible for the sum in both the sets to be equal. Hence the answer is “NO”.

# ALTERNATE EXPLANATION:

There is also another way to solve this problem

Take n \bmod 4 ( = n%4) and solve the problem manually for different cases.

Eg:

n = 1 → “NO”

n = 2 → “NO”

n = 3 → “YES” (1+2 , 3)

n = 4 → “YES” (1+4 , 2+3)

n = 5 → “NO”

n = 6 → “NO”

n = 7 → “YES” (1+2+5+6 , 3+4+7)

n = 8 → “YES” (1+4+5+8 , 2+3+6+7)

n = 9 → “NO”

n = 10 → “NO”

You may notice that this forms a pattern.

Here we can see that if (n%4) == 0 or (n%4) == 3, then the answer is “YES”

But if (n%4) == 1 or (n%4) == 2, then the answer is “NO”.

Proof:

Let’s see what can be done with the numbers n, n−1, n−2 and n−3. We can add n and n−3 in X and add n−1 and n−2 in Y. Then the difference between sums will definitely be 0. We can consider last four numbers this way until we have at least four numbers. And then we have a case n≤3. We can prove the solution for these four cases using bruteforce.

# SOLUTIONS:

## Setter's Solution

```
#include "bits/stdc++.h"
using namespace std;
int main()
{
int n;
cin >> n;
cout << ((((n * (n + 1)) / 2) & 1) ? "NO" : "YES") << endl;
return 0;
}
```

## Tester's Solution

```
#include "bits/stdc++.h"
using namespace std;
int main()
{
int n;
cin >> n;
n %= 4;
cout << ((n == 1 || n == 2) ? "NO" : "YES") << endl;
return 0;
}
```

## Editorialist's Solution

```
#include "bits/stdc++.h"
using namespace std;
int main()
{
int n;
cin >> n;
int sum = (n * (n + 1)) / 2; // formula for sum of first n natural numbers
if (sum % 2 == 0) // sum is even
cout << "YES";
else // sum is odd
cout << "NO";
return 0;
}
```