Two Sets

Your task is to divide the numbers 1,2,…,n$1,2,\dots ,n$ into two sets of equal sum.

If it is possible to divide then print YES and two sets.

If it is not possible to divide then print NO.

Example:

Input:  n = 7

Output:

YES
4
2 3 4 5 
3
6 7 1 

Approach:

Java

import java.util.HashSet;
import java.util.Iterator;

public class TwoSets {
    public static void main(String[] args) {
        int n = 7;

        twoSets(n);

    }

    static void twoSets(int n) {
        HashSet<Integer> st = new HashSet<Integer>();
        int sum = n * (n + 1) / 2;
        if (sum % 2 == 1)
            System.out.println("NO");
        else {

            sum = sum / 2;
            int ans = 0;
            int i;
            int x = 0;
            for (i = 1;; i++) {
                if (ans < sum) {
                    ans += i;
                    st.add((int) i);
                } else {
                    if (sum == ans)
                        break;
                    else {
                        x = ans - sum;
                        st.remove(x);
                        break;
                    }
                }
            }
            System.out.println("YES");
            System.out.println(st.size());
            Iterator<Integer> it = st.iterator();

            while (it.hasNext()) {

                System.out.print(it.next() + " ");
            }
            System.out.println();
            System.out.println(n - st.size());
            for (int j = i; j <= n; j++) {
                System.out.print(j + " ");
            }
            if (x > 0)
                System.out.println(x + " ");
        }
    }

}

C++

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

void twoSets(long long n)
{
    set<long long> st;
    long long sum = n * (n + 1) / 2;
    if (sum & 1)
        cout << "NO\n";
    else
    {

        sum = sum / 2;
        long long ans = 0;
        long long i;
        long long x = 0;
        for (i = 1;; i++)
        {
            if (ans < sum)
            {
                ans += i;
                st.insert(i);
            }
            else
            {
                if (sum == ans)
                    break;
                else
                {
                    x = ans - sum;
                    st.erase(x);
                    break;
                }
            }
        }
        cout << "YES\n";
        cout << st.size() << "\n";
        for (auto it = st.begin(); it != st.end(); it++)
            cout << *it << " ";
        cout << "\n";
        cout << n - st.size() << "\n";
        for (long long j = i; j <= n; j++)
        {
            cout << j << " ";
        }
        if (x)
            cout << x << " ";
    }
}
int main()
{
    long long n = 7;

    twoSets(n);

    return 0;
}