Distributing Natural Numbers into Two Sets with Equal Absolute Sum

Given N and M, distribute first N natural numbers in two sets such that the absolute sum of the numbers in the two sets is equal to M. If possible, print the sum of the numbers in the two sets separated by a space, otherwise, print “Not Possible“.

Examples:

Input : 7 4
Output : 16 12
Explanation : 
Sum of 7 natural numbers is (7 * (7 + 1) / 2 =) 28. 
Therefore if a and b be the sum of numbers in two sets then,
a + b = 28 and a - b = 4. 
Hence, a = (28 + 4)/2 = 16 and b = 28 - 16 = 12.
   
Input : 13 16
Output : Not Possible
Explanation : 
Sum of 13 natural numbers is (13 * (13 + 1) / 2 =) 91.
Therefore if a and b be the sum of numbers in two sets then,
a + b = 91 and a - b = 16. 
Hence, a = (91 + 16)/2 = 53.5. 
Therefore, distribution is not possible.

Approach:
An efficient approach would be to calculate the sum of N natural numbers by using the formula.

N * (N + 1) / 2

Therefore if a and b be the sum of numbers in two sets then, a + b = sum_of_natural_numbers and a – b = M. Solving the two equations we get

a = (sum_of_natural_numbers + M) / 2
b = sum_of_natural_numbers - a

But if (sum_of_natural_numbers + M) is odd, then a would be a fractional number, hence distribution is not possible. Therefore, distribution will only be possible when (sum_of_natural_numbers + M) is even.

Implementation in C++:

// CPP program to distribute N natural numbers in
// two sets such that the absolute sum of the
// numbers in the two sets is equal to M.

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

// Function to calculate sum of numbers in two sets
void sumOfSets(int N, int M)
{
    // Calculate sum of natural numbers
    int sum_of_natural_numbers = (N * (N + 1)) / 2;  
    // Checking if the sum is odd
    if ((sum_of_natural_numbers + M) & 1)            
    {
        cout << "Not Possible";
    }
    else
    {
        // Set 1
        int a = (sum_of_natural_numbers + M) / 2; 
        // Set 2  
        int b = sum_of_natural_numbers - a;         
        cout << a << " " << b;
    }
}

int main()
{
    int N = 10, M = 11;
    sumOfSets(N, M);
    return 0;
}

Output:

33 22

Time Complexity: O(1)

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.