First N natural can be divided into two sets with given difference and co-prime sums

Given first N natural numbers. Our task is to check whether is it possible to split the numbers in two sets such that absolute difference of the sum of numbers in the two sets is equal to M and their gcd(greatest common divisor) is 1.

Examples:

Input : 5 7
Output : Yes
Here,N=5 and M=7
Total sum of N numbers = 15.
So we can have two sets with their sum 11 and 4 respectively,
whose absolute difference = 7 (= M ) and gcd of 11 and 4 = 1.

Input : 8 9
Output : No
Here, total sum = 36.
We can not split numbers in two sets, 
whose absolute difference = 9 (= M ).

Input : 4 6
Output : No

Approach: Suppose Su1 and Su2 be the two set of numbers.

Sum(Su1) + Sum(Su2) = N(N*1)/2 (Sum of first N natural numbers).
Sum(Su1) - Sum(Su2) = M.

So by solving this simultaneous linear equation,we can find Sum(Su1) and Sum(Su2).
If Sum(Su1) and Sum(Su2) are integers and their gcd = 1, then we will print Yes else No.

Below is the C++ implementation:

#include <bits/stdc++.h>
using namespace std;
#define ll long long // for simplicity

// Euclidean function for GCD
int gcd(ll a, ll b) {
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

// Function to check if it's possible to make two sets
string check(ll n, ll m) {
    ll sumN = (n * (n + 1)) / 2; // Sum of first n natural numbers
    // By solving the equation su1 + su2 = sumN and su1 - su2 = m
    ll su1 = (sumN + m) / 2;
    ll su2 = (sumN - m) / 2;

    // If Sum(Su1) and Sum(Su2) are integers and their GCD = 1, then return "Yes"
    if (su1 + su2 == sumN && su1 - su2 == m && gcd(su1, su2) == 1)
        return "Yes";
    else
        return "No";
}

// Driver program to test the above function
int main() {
    ll n = 5, m = 7;
    cout << check(n, m) << endl;
    return 0;
}

Output:

Yes

Time Complexity: O(log(min(su1, su2)))

Space 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.