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

**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 <bits/stdc++.h> ` `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

`<?php ` `/* PHP 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*/` ` ` `function` `__gcd (` `$a` `, ` `$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. ` `function` `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` `&& ` ` ` `$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))

## leave a comment

## 0 Comments