Dado un número entero N , la tarea es crear dos conjuntos de elementos distintos de 1 a N tales que el mcd de sus respectivas sumas sea mayor que 1. Imprime los conjuntos respectivos. Si no se puede hacer tal división, imprima -1.
Ejemplos:
Entrada: N = 5
Salida:
2 4
1 3 5
Explicación:
MCD(Suma({2, 4}), Suma({1, 3, 5}) = MCD(6, 9) = 3Entrada: N = 2
Salida: -1
Explicación:
Para N = 2, no es posible dividir en dos conjuntos cuyo MCD de su suma sea mayor que 1.
Enfoque 1: un enfoque simple es dividir todos los números pares hasta N en un conjunto y todos los números impares en otro conjunto.
El siguiente código es la implementación del enfoque:
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
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Enfoque 2: Este enfoque se puede dividir en 2 casos basados en N:
- Si N es impar:
- La suma de N números naturales es divisible por (N+1)/2 en este caso.
- Por lo tanto, solo necesitamos poner (N+1)/2 en el primer conjunto y los números restantes en el segundo conjunto.
- Esto hará automáticamente que el GCD de sus sumas sea mayor que 1.
- Si N es par:
- La suma de N números naturales es divisible por N/2 en este caso.
- Por lo tanto, solo necesitamos poner N/2 en el primer conjunto y los números restantes en el segundo conjunto.
- Esto hará automáticamente que el GCD de sus sumas sea mayor que 1.
A continuación se muestra la implementación del enfoque anterior:
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
Complejidad de Tiempo: O(N)
Complejidad de Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por mridulkumar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA