Split N natural numbers into two sets having GCD of their sums greater than 1
Given an integer N, the task is to create two sets of distinct elements from 1 to N such that the gcd of their respective sums is greater than 1. Print the respective sets. If no such split can be done, print -1.
Examples:
Input: N = 5
Output:
2 4
1 3 5
Explanation:
GCD(Sum({2, 4}), Sum({1, 3, 5}) = GCD(6, 9) = 3Input: N = 2
Output: -1
Explanation:
For N = 2, it is not possible to divide into two sets having GCD of their sum greater than 1.
Approach 1: A simple approach is to split all even numbers up to N into one set and all odd numbers into another set.
Below code is the implementation of the approach:
C++
// C++ program to split N natural numbers // into two sets having GCD // of their sums greater than 1 #include <bits/stdc++.h> using namespace std; // Function to create // and print the two sets void createSets( int N) { // No such split // possible for N <= 2 if (N <= 2) { cout << "-1" << endl; return ; } // Print the first set // consisting of even elements for ( int i = 2; i <= N; i += 2) cout << i << " " ; cout << "\n" ; // Print the second set // consisting of odd ones for ( int i = 1; i <= N; i += 2) { cout << i << " " ; } } // Driver Code int main() { int N = 6; createSets(N); return 0; } |
Java
// Java program to split N natural numbers // into two sets having GCD // of their sums greater than 1 class GFG{ // Function to create // and print the two sets static void createSets( int N) { // No such split // possible for N <= 2 if (N <= 2 ) { System.out.println( "-1" ); return ; } // Print the first set // consisting of even elements for ( int i = 2 ; i <= N; i += 2 ) System.out.print(i + " " ); System.out.print( "\n" ) ; // Print the second set // consisting of odd ones for ( int i = 1 ; i <= N; i += 2 ) { System.out.print(i + " " ); } } // Driver Code public static void main(String[] args) { int N = 6 ; createSets(N); } } // This code is contributed by shivanisinghss2110 |
Python3
# Python3 program to split N natural numbers # into two sets having GCD # of their sums greater than 1 # Function to create # and print the two sets def createSets(N): # No such split # possible for N <= 2 if (N < = 2 ): print ( "-1" ); return ; # Print the first set # consisting of even elements for i in range ( 2 , N + 1 , 2 ): print (i, end = " " ); print (""); # Print the second set # consisting of odd ones for i in range ( 1 , N + 1 , 2 ): print (i, end = " " ); # Driver Code if __name__ = = '__main__' : N = 6 ; createSets(N); # This code is contributed by gauravrajput1 |
C#
// C# program to split N natural numbers // into two sets having GCD // of their sums greater than 1 using System; class GFG{ // Function to create // and print the two sets static void createSets( int N) { // No such split // possible for N <= 2 if (N <= 2) { Console.WriteLine( "-1" ); return ; } // Print the first set // consisting of even elements for ( int i = 2; i <= N; i += 2) Console.Write(i + " " ); Console.Write( "\n" ) ; // Print the second set // consisting of odd ones for ( int i = 1; i <= N; i += 2) { Console.Write(i + " " ); } } // Driver Code public static void Main(String[] args) { int N = 6; createSets(N); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // Javascript program to split N natural numbers // into two sets having GCD // of their sums greater than 1 // Function to create // and print the two sets function createSets(N) { // No such split // possible for N <= 2 if (N <= 2) { document.write( "-1" ); return ; } // Print the first set // consisting of even elements for (let i = 2; i <= N; i += 2) document.write(i + " " ); document.write( "</br>" ); // Print the second set // consisting of odd ones for (let i = 1; i <= N; i += 2) { document.write(i + " " ); } } let N = 6; createSets(N); </script> |
2 4 6 1 3 5
Time Complexity: O(N)
Auxiliary Space: O(1),since no extra space has been taken.
Approach 2: This approach can be divided into 2 cases based on N:
- If N is odd:
- The sum of N natural numbers is divisible by (N+1)/2 in this case.
- Therefore we only need to put (N+1)/2 into first set and the remaining numbers into second set.
- This will automatically make the GCD of their sums greater than 1.
- If N is even:
- The sum of N natural numbers is divisible by N/2 in this case.
- Therefore we only need to put N/2 into first set and the remaining numbers into second set.
- This will automatically make the GCD of their sums greater than 1.
Below is the implementation of the above approach:
C++
// C++ program to split N natural numbers // into two sets having GCD // of their sums greater than 1 #include <bits/stdc++.h> using namespace std; #define ll long long // Function to create // and print the two sets void createSets(ll n) { // For n <= 2 such sets // can never be formed if (n <= 2) { cout << "-1" ; return ; } else { // Check if N is even or odd // and store the element // which divides the sum of N // natural numbers accordingly ll x = (n % 2 == 0) ? (n / 2) : ((n + 1) / 2); // First set cout << x << endl; // Print elements of second set for (ll i = 1; i <= n; i++) { if (i == x) continue ; cout << i << " " ; } } return ; } // Driver code int main() { ll N = 7; createSets(N); return 0; } |
Java
// Java program to split N natural numbers // into two sets having GCD // of their sums greater than 1 class GFG{ // Function to create // and print the two sets static void createSets( long n) { // For n <= 2 such sets // can never be formed if (n <= 2 ) { System.out.print( "-1" ); return ; } else { // Check if N is even or odd // and store the element // which divides the sum of N // natural numbers accordingly long x = (n % 2 == 0 ) ? (n / 2 ) : ((n + 1 ) / 2 ); // First set System.out.print(x + "\n" ); // Print elements of second set for ( int i = 1 ; i <= n; i++) { if (i == x) continue ; System.out.print(i + " " ); } } return ; } // Driver code public static void main(String[] args) { long N = 7 ; createSets(N); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to split N natural numbers # into two sets having GCD # of their sums greater than 1 # Function to create # and print the two sets def createSets(n): # For n <= 2 such sets # can never be formed if (n < = 2 ): print ( "-1" ); return ; else : # Check if N is even or odd # and store the element # which divides the sum of N # natural numbers accordingly x = (n / / 2 ) if (n % 2 = = 0 ) else ( (n + 1 ) / / 2 ); # First set print (x, " " ); # Print elements of second set for i in range ( 1 , n + 1 ): if (i = = x): continue ; print (i, end = " " ); return ; # Driver code if __name__ = = '__main__' : N = 7 ; createSets(N); # This code is contributed by 29AjayKumar |
C#
// C# program to split N natural numbers // into two sets having GCD // of their sums greater than 1 using System; class GFG{ // Function to create // and print the two sets static void createSets( long n) { // For n <= 2 such sets // can never be formed if (n <= 2) { Console.Write( "-1" ); return ; } else { // Check if N is even or odd // and store the element // which divides the sum of N // natural numbers accordingly long x = (n % 2 == 0) ? (n / 2) : ((n + 1) / 2); // First set Console.Write(x + "\n" ); // Print elements of second set for ( int i = 1; i <= n; i++) { if (i == x) continue ; Console.Write(i + " " ); } } return ; } // Driver code public static void Main(String[] args) { long N = 7; createSets(N); } } // This code is contributed by sapnasingh4991 |
Javascript
<script> // Javascript program to split N natural numbers // into two sets having GCD // of their sums greater than 1 // Function to create // and print the two sets function createSets(n) { // For n <= 2 such sets // can never be formed if (n <= 2) { document.write( "-1" ); return ; } else { // Check if N is even or odd // and store the element // which divides the sum of N // natural numbers accordingly let x = (n % 2 == 0) ? (n / 2) : ((n + 1) / 2); // First set document.write(x + "</br>" ); // Print elements of second set for (let i = 1; i <= n; i++) { if (i == x) continue ; document.write(i + " " ); } } return ; } // Driver code let N = 7; createSets(N); // This code is contributed by suresh07. </script> |
4 1 2 3 5 6 7
Time Complexity: O(N)
Auxiliary Space Complexity: O(1)