Dado un número entero N ( N &e; 3 ), la tarea es dividir todos los números del 1 al N en dos subsecuencias de modo que la suma de las dos subsecuencias no sea coprima entre sí.
Ejemplos:
Entrada: N = 5
Salida:
{1, 3, 5}
{2, 4}
Explicación: Suma de la subsecuencia X[] = 1 + 3 + 5 = 9.
Suma de la subsecuencia Y[] = 2 + 4 = 6 Como MCD(9 ,
6) es 3, las sumas no son coprimos entre sí.Entrada: N = 4
Salida:
{1, 4}
{2, 3}
Enfoque ingenuo: el enfoque más simple es dividir los primeros N números naturales en dos subsecuencias de todas las formas posibles y, para cada combinación, verificar si la suma de ambas subsecuencias no es coprima o no. SI se encuentra que es cierto para cualquier par de subsecuencias, imprima esa subsecuencia y salga del bucle .
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
- La suma de los primeros (N – 1) números naturales viene dada por (N*(N – 1))/2 .
- Por lo tanto, MCD de ((N*(N – 1))/2) y N es N .
De la observación anterior, inserte todos los números del rango [1, N] en una subsecuencia y N en otra subsecuencia.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to split 1 to N into two subsequences with // non-coprime sums void printSubsequence(int N) { cout << "{ "; for (int i = 1; i < N - 1; i++) cout << i << ", "; cout << N - 1 << " }\n"; cout << "{ " << N << " }"; } // Driver Code int main() { int N = 8; printSubsequence(N); return 0; } // This code is contributed by Sania Kumari Gupta
C
// C program for the above approach #include <stdio.h> // Function to split 1 to N into two subsequences with // non-coprime sums void printSubsequence(int N) { printf("{ "); for (int i = 1; i < N - 1; i++) printf("%d ", i); printf("%d}\n", N - 1); printf("{%d}",N); } // Driver Code int main() { int N = 8; printSubsequence(N); return 0; } // This code is contributed by Sania Kumari Gupta
Java
// Java program for the above approach class GFG { // Function to split 1 to N // into two subsequences // with non-coprime sums public static void printSubsequence(int N) { System.out.print("{ "); for (int i = 1; i < N - 1; i++) { System.out.print(i + ", "); } System.out.println(N - 1 + " }"); System.out.print("{ " + N + " }"); } // Driver code public static void main(String[] args) { int N = 8; printSubsequence(N); } } // This code is contributed by divyesh072019
Python3
# Python3 program for the above approach # Function to split 1 to N # into two subsequences # with non-coprime sums def printSubsequence(N): print("{ ", end = "") for i in range(1, N - 1): print(i, end = ", ") print(N - 1, end = " }\n") print("{", N, "}") # Driver Code if __name__ == '__main__': N = 8 printSubsequence(N) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach using System; class GFG { // Function to split 1 to N // into two subsequences // with non-coprime sums public static void printSubsequence(int N) { Console.Write("{ "); for (int i = 1; i < N - 1; i++) { Console.Write(i + ", "); } Console.WriteLine(N - 1 + " }"); Console.Write("{ " + N + " }"); } // Driver code public static void Main(string[] args) { int N = 8; printSubsequence(N); } } // This code is contributed by AnkThon
Javascript
<script> // Javascript program for the above approach // Function to split 1 to N // into two subsequences // with non-coprime sums function printSubsequence(N) { document.write("{ "); for (let i = 1; i < N - 1; i++) { document.write(i + ", "); } document.write(N - 1 + " }" + "</br>"); document.write("{ " + N + " }" + "</br>"); } let N = 8; printSubsequence(N); </script>
{ 1, 2, 3, 4, 5, 6, 7 } { 8 }
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shekabhi1208 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA