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

Given N and M, task is to find whether numbers 1 to N can be divided into two sets such that the absolute difference between the sum of two sets is M and gcd of the sum of two sets is 1 (i.e. Sum of both sets are co-prime).

Prerequisite : GCD in CPP | GCD

Examples :

Input : N = 5 and M = 7
Output : YES
Explanation : as numbers from 1 to 5 can be divided into two sets {1, 2, 3, 5} and {4} such that absolute difference between the sum of both sets is 11 – 4 = 7 which is equal to M and also GCD(11, 4) = 1.

Input : N = 6 and M = 3
Output : NO
Explanation : In this case, Numbers from 1 to 6 can be divided into two sets {1, 2, 4, 5} and {3, 6} such that absolute difference between their sum is 12 – 9 = 3. But, since 12 and 9 are not co-prime as GCD(12, 9) = 3, the answer is ‘NO’.

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach : Since we have 1 to N numbers, we know that the sum of all the numbers is N * (N + 1) / 2. Let S1 and S2 be two sets such that,
1) sum(S1) + sum(S2) = N * (N + 1) / 2
2) sum(S1) – sum(S2) = M
Solving these two equations will give us the sum of both the sets. If sum(S1) and sum(S2) are integers and they are co-prime (their GCD is 1), then there exists a way to split the numbers into two sets. Otherwise, there is no way to split these N numbers.

Below is the implementation of the solution described above.

## C++

 `/* CPP code to determine whether numbers ` `   ``1 to N can be divided into two sets ` `   ``such that absolute difference between  ` `   ``sum of these two sets is M and these ` `   ``two sum are co-prime*/` `#include ` `using` `namespace` `std; ` ` `  `// function that returns boolean value ` `// on the basis of whether it is possible ` `// to divide 1 to N numbers into two sets ` `// that satisfy given conditions. ` `bool` `isSplittable(``int` `n, ``int` `m) ` `{ ` `    ``// initializing total sum of 1 ` `    ``// to n numbers ` `    ``int` `total_sum = (n * (n + 1)) / 2; ` ` `  `    ``// since (1) total_sum = sum_s1 + sum_s2 ` `    ``// and (2) m = sum_s1 - sum_s2 ` `    ``// assuming sum_s1 > sum_s2. ` `    ``// solving these 2 equations to get ` `    ``// sum_s1 and sum_s2 ` `    ``int` `sum_s1 = (total_sum + m) / 2; ` ` `  `    ``// total_sum = sum_s1 + sum_s2 ` `    ``// and therefore ` `    ``int` `sum_s2 = total_sum - sum_s1; ` ` `  `    ``// if total sum is less than the absolute ` `    ``// difference then there is no way we ` `    ``// can split n numbers into two sets ` `    ``// so return false ` `    ``if` `(total_sum < m) ` `        ``return` `false``; ` ` `  `    ``// check if these two sums are ` `    ``// integers and they add up to ` `    ``// total sum and also if their ` `    ``// absolute difference is m. ` `    ``if` `(sum_s1 + sum_s2 == total_sum && ` `        ``sum_s1 - sum_s2 == m) ` ` `  `        ``// Now if two sum are co-prime ` `        ``// then return true, else return false. ` `        ``return` `(__gcd(sum_s1, sum_s2) == 1); ` ` `  `    ``// if two sums don't add up to total ` `    ``// sum or if their absolute difference ` `    ``// is not m, then there is no way to ` `    ``// split n numbers, hence return false ` `    ``return` `false``; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `n = 5, m = 7; ` ` `  `    ``// function call to determine answer ` `    ``if` `(isSplittable(n, m)) ` `        ``cout << ``"Yes"``; ` `    ``else` `        ``cout << ``"No"``; ` ` `  `    ``return` `0; ` `} `

## Java

 `/* Java code to determine whether numbers ` `1 to N can be divided into two sets ` `such that absolute difference between  ` `sum of these two sets is M and these ` `two sum are co-prime*/` `class` `GFG  ` `{ ` `    ``static` `int` `GCD (``int` `a, ``int` `b) ` `    ``{ ` `        ``return` `b == ``0` `? a : GCD(b, a % b); ` `    ``} ` `     `  `    ``// function that returns boolean value ` `    ``// on the basis of whether it is possible ` `    ``// to divide 1 to N numbers into two sets ` `    ``// that satisfy given conditions. ` `    ``static` `boolean` `isSplittable(``int` `n, ``int` `m) ` `    ``{ ` `         `  `        ``// initializing total sum of 1 ` `        ``// to n numbers ` `        ``int` `total_sum = (n * (n + ``1``)) / ``2``; ` `     `  `        ``// since (1) total_sum = sum_s1 + sum_s2 ` `        ``// and (2) m = sum_s1 - sum_s2 ` `        ``// assuming sum_s1 > sum_s2. ` `        ``// solving these 2 equations to get ` `        ``// sum_s1 and sum_s2 ` `        ``int` `sum_s1 = (total_sum + m) / ``2``; ` `     `  `        ``// total_sum = sum_s1 + sum_s2 ` `        ``// and therefore ` `        ``int` `sum_s2 = total_sum - sum_s1; ` `     `  `        ``// if total sum is less than the absolute ` `        ``// difference then there is no way we ` `        ``// can split n numbers into two sets ` `        ``// so return false ` `        ``if` `(total_sum < m) ` `            ``return` `false``; ` `     `  `        ``// check if these two sums are ` `        ``// integers and they add up to ` `        ``// total sum and also if their ` `        ``// absolute difference is m. ` `        ``if` `(sum_s1 + sum_s2 == total_sum && ` `                    ``sum_s1 - sum_s2 == m) ` `     `  `            ``// Now if two sum are co-prime ` `            ``// then return true, else return false. ` `            ``return` `(GCD(sum_s1, sum_s2) == ``1``); ` ` `  `        ``// if two sums don't add up to total ` `        ``// sum or if their absolute difference ` `        ``// is not m, then there is no way to ` `        ``// split n numbers, hence return false ` `        ``return` `false``; ` `    ``} ` `     `  `    ``// Driver Code ` `    ``public` `static` `void` `main(String args[])  ` `    ``{ ` `        ``int` `n = ``5``, m = ``7``; ` ` `  `        ``// function call to determine answer ` `        ``if` `(isSplittable(n, m)) ` `            ``System.out.println(``"Yes"``); ` `        ``else` `            ``System.out.println(``"No"``); ` `         `  `    ``} ` `} ` ` `  `// This code is contributed by Sam007 `

## Python3

# Python3 code to determine whether numbers
# 1 to N can be divided into two sets
# such that absolute difference between
# sum of these two sets is M and these
# two sum are co-prime

def __gcd (a, b):

return a if(b == 0) else __gcd(b, a % b);

# function that returns boolean value
# on the basis of whether it is possible
# to divide 1 to N numbers into two sets
# that satisfy given conditions.
def isSplittable(n, m):

# initializing total sum of 1
# to n numbers
total_sum = (int)((n * (n + 1)) / 2);

# since (1) total_sum = sum_s1 + sum_s2
# and (2) m = sum_s1 – sum_s2
# assuming sum_s1 > sum_s2.
# solving these 2 equations to get
# sum_s1 and sum_s2
sum_s1 = int((total_sum + m) / 2);

# total_sum = sum_s1 + sum_s2
# and therefore
sum_s2 = total_sum – sum_s1;

# if total sum is less than the absolute
# difference then there is no way we
# can split n numbers into two sets
# so return false
if (total_sum < m): return False; # check if these two sums are # integers and they add up to # total sum and also if their # absolute difference is m. if (sum_s1 + sum_s2 == total_sum and sum_s1 - sum_s2 == m): # Now if two sum are co-prime # then return true, else return false. return (__gcd(sum_s1, sum_s2) == 1); # if two sums don't add up to total # sum or if their absolute difference # is not m, then there is no way to # split n numbers, hence return false return False; # Driver code n = 5; m = 7; # function call to determine answer if (isSplittable(n, m)): print("Yes"); else: print("No"); # This code is contributed by mits [tabby title="C#"]

 `/* C# code to determine whether numbers ` `1 to N can be divided into two sets ` `such that absolute difference between  ` `sum of these two sets is M and these ` `two sum are co-prime*/` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``static` `int` `GCD (``int` `a, ``int` `b) ` `    ``{ ` `        ``return` `b == 0 ? a : GCD(b, a % b); ` `    ``} ` `     `  `    ``// function that returns boolean value ` `    ``// on the basis of whether it is possible ` `    ``// to divide 1 to N numbers into two sets ` `    ``// that satisfy given conditions. ` `    ``static` `bool` `isSplittable(``int` `n, ``int` `m) ` `    ``{ ` `         `  `        ``// initializing total sum of 1 ` `        ``// to n numbers ` `        ``int` `total_sum = (n * (n + 1)) / 2; ` `     `  `        ``// since (1) total_sum = sum_s1 + sum_s2 ` `        ``// and (2) m = sum_s1 - sum_s2 ` `        ``// assuming sum_s1 > sum_s2. ` `        ``// solving these 2 equations to get ` `        ``// sum_s1 and sum_s2 ` `        ``int` `sum_s1 = (total_sum + m) / 2; ` `     `  `        ``// total_sum = sum_s1 + sum_s2 ` `        ``// and therefore ` `        ``int` `sum_s2 = total_sum - sum_s1; ` `     `  `        ``// if total sum is less than the absolute ` `        ``// difference then there is no way we ` `        ``// can split n numbers into two sets ` `        ``// so return false ` `        ``if` `(total_sum < m) ` `            ``return` `false``; ` `     `  `        ``// check if these two sums are ` `        ``// integers and they add up to ` `        ``// total sum and also if their ` `        ``// absolute difference is m. ` `        ``if` `(sum_s1 + sum_s2 == total_sum && ` `                       ``sum_s1 - sum_s2 == m) ` `     `  `            ``// Now if two sum are co-prime ` `            ``// then return true, else return false. ` `            ``return` `(GCD(sum_s1, sum_s2) == 1); ` ` `  `        ``// if two sums don't add up to total ` `        ``// sum or if their absolute difference ` `        ``// is not m, then there is no way to ` `        ``// split n numbers, hence return false ` `        ``return` `false``; ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `n = 5, m = 7; ` ` `  `        ``// function call to determine answer ` `        ``if` `(isSplittable(n, m)) ` `            ``Console.Write(``"Yes"``); ` `        ``else` `            ``Console.Write(``"No"``); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007. `

## PHP

 ` sum_s2. ` `    ``// solving these 2 equations to get ` `    ``// sum_s1 and sum_s2 ` `    ``\$sum_s1` `= (int)((``\$total_sum` `+ ``\$m``) / 2); ` ` `  `    ``// total_sum = sum_s1 + sum_s2 ` `    ``// and therefore ` `    ``\$sum_s2` `= ``\$total_sum` `- ``\$sum_s1``; ` ` `  `    ``// if total sum is less than the absolute ` `    ``// difference then there is no way we ` `    ``// can split n numbers into two sets ` `    ``// so return false ` `    ``if` `(``\$total_sum` `< ``\$m``) ` `        ``return` `false; ` ` `  `    ``// check if these two sums are ` `    ``// integers and they add up to ` `    ``// total sum and also if their ` `    ``// absolute difference is m. ` `    ``if` `(``\$sum_s1` `+ ``\$sum_s2` `== ``\$total_sum` `&& ` `        ``\$sum_s1` `- ``\$sum_s2` `== ``\$m``) ` ` `  `        ``// Now if two sum are co-prime ` `        ``// then return true, else return false. ` `        ``return` `(__gcd(``\$sum_s1``, ``\$sum_s2``) == 1); ` ` `  `    ``// if two sums don't add up to total ` `    ``// sum or if their absolute difference ` `    ``// is not m, then there is no way to ` `    ``// split n numbers, hence return false ` `    ``return` `false; ` `} ` ` `  `// Driver code ` `\$n` `= 5; ` `\$m` `= 7; ` ` `  `// function call to determine answer ` `if` `(isSplittable(``\$n``, ``\$m``)) ` `    ``echo` `"Yes"``; ` `else` `    ``echo` `"No"``; ` ` `  `// This Code is Contributed by mits ` `?> `

Output:

```Yes
```

Time Complexity : O(log(n))

This article is attributed to GeeksforGeeks.org

code

load comments