Question
Given a positive integer n, n > 2. The task is to divide numbers from 1 to n in two groups such that the absolute difference of the sum of each group is minimum.
Input: An integer n.
Output: Print the size of any of the two groups in the first line, then print the elements of that group in the second line. Similarly, print the size of the remaining group in the next line and then its elements.
The questions you should ask the interviewer:
 What is the constraint on n?
 If there are multiple groups possible, how to give output in that case?
Examples:
Alert Ninjas: Don't stop now! Enroll in the Competitive Programming course today and start coding. Learn the art of writing time and spaceefficient code and compete in code competitions worldwide.
Input: 5
Explanation: Group 1 has sum 7, and group 2 has sum 8. Their absolute difference is one, which is the smallest possible. Multiple correct responses are possible. Other groups can be (1, 2, 5) and (3, 4).
Input: 6 Output: 4 5 3 2 1 
Recommended: Please try to solve it yourself before moving on to the solution.
Also see, Euclid GCD Algorithm
Solution:
Approach 1:
Idea: The idea is to use the fact that we can always divide 1 to n into two groups such that the absolute minimum difference of the sum is either 0 or 1. As the sum of all 'N' elements will be either odd or even. So partition will be,
 if the total sum is odd => odd = odd + even, in this case, the absolute minimum difference can be 1.

if the total sum is even => even = o+o / e+ e, in this case, the absolute minimum difference can be 0.
Implementation
 Consider two groups Group1 and Group2.
 We define a variable halfSum as half of the sum of n components.

Now, in a loop from n to 1, enter i into group1 if the sum of the elements in group1 does not exceed halfSum; otherwise, insert that i into group2.
C++
#include <bits/stdc++.h> using namespace std; // To print the given output. void print(vector<int> &A) { cout << A.size() << endl; for (int i = 0; i < A.size(); i++) cout << A[i] << " "; cout << endl; } void findGroup(int n) { // sum of numbers 1 to n is n*(n+1)/2. Proof by induction. int sum = n * (n + 1) / 2; // Sum of elements of group1. int halfSum = sum / 2; int sumGroup1 = 0; vector<int> group1, group2; for (int i = n; i > 0; i) { if (sumGroup1 + i <= halfSum) { group1.push_back(i); sumGroup1 = sumGroup1 + i; } else { group2.push_back(i); } } // Print both the groups print(group1); print(group2); } // Driver program to test above functions int main() { int n = 6; findGroup(n); return 0; } 
Output:
Time Complexity: O(N) as we are only using a for loop from range 1 to n, which uses O(N) time.
Space Complexity: The space complexity is O(N) as we are using extra space to create two groups of maximum size n.
Approach2:
Idea: As the elements are consecutive, we can always say that in a series of four continuous elements, the sum of extremes is always equal to the sum of middle elements.
Example:
1 2 3 4
1+4 = 2+3 = 5
5 6 7 8
5+8 = 6+7 = 13
And so on…
Implementation:
 Check if n is odd or even.
 If odd, divide the elements 1 to n in pairs. E.g., add (1,2) in group1, (3,4) in group2, then (5,6) in group1, and so on.
 If even, consider the groups of 4. Add the extremes to one group and the central elements to the other group. There can be a chance that two elements remain in the end; add oneone element to each group.
C++
#include <bits/stdc++.h> // if n is odd. // if n is even
// add i,i+3 in one group and i+1,i+2 in other group 
Output:
Time Complexity: O(N)
Space Complexity: The space complexity is O(N) as we are using extra space to create two groups of maximum size n.
Check out this problem  Pair Sum In Array.