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

0 0 9 minutes read

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

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
?>

Javascript

<script>
 
/* Javascript 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
    let total_sum = parseInt((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
    let sum_s1 = parseInt((total_sum + m) / 2);
 
    // total_sum = sum_s1 + sum_s2
    // and therefore
    let 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
let n = 5;
let m = 7;
 
// function call to determine answer
if (isSplittable(n, m))
    document.write("Yes");
else
    document.write("No");
 
// This Code is Contributed by _saurabh_jaiswal
 
</script>

Output:

Yes

Time Complexity : O(log(n))
Auxiliary Space: O(1)

Please suggest if someone has a better solution which is more efficient in terms of space and time.
This article is contributed by Aarti_Rathi. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!