Two Sets

Two Sets

Ramandeep Singh's photo
Ramandeep Singh
·

2 min read

Your task is to divide the numbers (1,2,3,....n) into two sets of equal sum.

The only input line contains an integer n.

Input

The only input line contains an integer n.

Output:

Print "YES", if the division is possible, and "NO" otherwise.

After this, if the division is possible, print an example of how to create the sets. First, print the number of elements in the first set followed by the elements themselves in a separate line, and then, print the second set in a similar way.

Constraints

  • 1≤n≤106

Example 1

Input:

7

Output:

YES
4
1 2 4 7
3
3 5 6

Example 2

Input:

6

Output:

NO

To solve this problem, we need to just divide the given set into two parts such that the sum of numbers in both parts is the same .

To solve this problem, we have to just brute force the problem i.e. just start putting up the values such that you just push values from the last till you do not exceed the (sum/2) , Let's understand this with an example.

Let's say we have N = 7, Now, we know that we cannot exceed value (7*(8))/2 = 28.

Let's start adding values from the end i.e. (7 + 6 + 5 + 4 + .. ) till we do not exceed 28 say we have k and we also have t.

So, to solve this problem, we need to keep adding till the values exceed 28,

So we add till the sum exceed 28 and we also mark the given numbers using a boolean array.

Let's say the sum desired is s , then we push (s - k) into the array.

Let's code the solution

#include<bits/stdc++.h>
using namespace std;

int main(){
      int n;
      cin >> n;
 int sum = n*(n+1)/2;

    if(sum % 2 == 0)
    {
        cout << "YES\n";
       int s = sum/2;

       vi a , b;
       int k = 0;
       int t = n;

       vector<bool>bul(n+1,false);
       while(k+t < s)
       {
             a.push_back(t);
             bul[t] = true;
             k += t;
             t--;
       }

      if(k < s)
      {
          a.push_back(s-k);
          bul[s-k] = true;
      }



      for(int i = 1; i <= n; i++)
      {
          if(!bul[i])
              b.push_back(i);
      }
      cout << a.size() << endl;
     for(int i=0;i<a.size(); i++)
     cout << a[i];
      cout << endl;
      cout << b.size() << endl;

     for(int i=0;i<
      out(b[i]);


    }
    else
    {
        cout << "NO\n";
    }

}
#ArtiDSA