Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar todos los máximos comunes divisores (MCD) distintos posibles entre todas las subsecuencias no vacías de la array arr[] .
Ejemplos:
Entrada: arr[] = {3, 4, 8}
Salida: 1 3 4 8
Explicación:
Las subsecuencias no vacías posibles son {3}, {4}, {8}, {3, 4}, {4, 8 }, {3, 8}, {3, 4, 8} y sus GCD correspondientes son 3, 4, 8, 1, 4, 1, 1.
Por lo tanto, imprime todos los GCD como {1, 3, 4, 8} .Entrada: arr[] = {3, 8, 9, 4, 13, 45, 6}
Salida: 1 2 3 4 6 8 9 13 45
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las subsecuencias posibles de la array dada y almacenar todos los GCD de la subsecuencia en un conjunto . Después de verificar todas las subsecuencias, imprima las tiendas de elementos en el conjunto como todos los GCD posibles que se pueden formar.
Complejidad de tiempo: O(log M*2 N ), donde M es el elemento máximo de la array .
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando el enfoque codicioso al observar el hecho de que el GCD de cualquier subsecuencia se encuentra en el rango [1, M] donde M es el elemento máximo de la array. Por lo tanto, la idea es iterar sobre el rango [1, M] y si algún elemento en el rango es un factor de un elemento de array, imprima el elemento actual como uno de los GCD resultantes . Siga los pasos a continuación para resolver el problema:
- Almacene todos los elementos de la array en HashSet , digamos s .
- Iterar sobre el rango [1, M] usando la variable i y realizar los siguientes pasos:
- Iterar a través de todos los múltiplos de i , si existe algún múltiplo que esté presente en el HashSet, luego imprima el elemento actual i como uno de los posibles GCD.
A continuación se muestra una implementación del enfoque anterior:
// programa C++ para el enfoque anterior
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the different GCDs of // the subsequence of the given array void findGCDsSubsequence(vector<int> arr) { // Stores all the possible GCDs vector<int> ans; // Stores all array element in set set<int> s; for(int i : arr) s.insert(i); int M = *max_element(arr.begin(), arr.end()); // Iterate over the range [1, M] for(int i = 1; i <= M; i++) { int gcd = 0; // Check if i can be the GCD of // any subsequence for(int j = i; j < M + 1; j += i) { if (s.find(j) != s.end()) gcd = __gcd(gcd, j); } if (gcd == i) ans.push_back(i); } for(int i = 0; i < ans.size(); i++) cout << ans[i] << " "; } // Driver Code int main() { int N = 7; vector<int> arr = { 3, 4, 8 }; // Function Call findGCDsSubsequence(arr); return 0; } // This code is contributed by parthagarwal1962000
Java
// Java program for the above approach import java.util.*; public class GFG { static int gcd1(int a, int b) { return b == 0 ? a : gcd1(b, a % b); } // Function to find the different GCDs of // the subsequence of the given array static void findGCDsSubsequence(ArrayList<Integer> arr) { // Stores all the possible GCDs ArrayList<Integer> ans = new ArrayList<Integer>(); // Stores all array element in set HashSet<Integer> s = new HashSet<Integer>(); for(int i : arr) s.add(i); int M = Integer.MIN_VALUE; for(int i : arr) { if (i > M) M = i; } // Iterate over the range [1, M] for(int i = 1; i <= M; i++) { int gcd = 0; // Check if i can be the GCD of // any subsequence for(int j = i; j < M + 1; j += i) { if (s.contains(j)) gcd = gcd1(gcd, j); } if (gcd == i) ans.add(i); } for(int i = 0; i < ans.size(); i++) System.out.print(ans.get(i) + " "); } // Driver Code public static void main(String args[]) { ArrayList<Integer> arr = new ArrayList<Integer>(); arr.add(3); arr.add(4); arr.add(8); // Function Call findGCDsSubsequence(arr); } } // This code is contributed by SoumikMondal
Python3
# Python3 program for the above approach import math # Function to find the different GCDs of # the subsequence of the given array def findGCDsSubsequence(nums): # Stores all the possible GCDs Ans = [] # Stores all array element in set s = set(nums) # Find the maximum array element M = max(nums) # Iterate over the range [1, M] for i in range(1, M + 1): # Stores the GCD of subsequence gcd = 0 # Check if i can be the GCD of # any subsequence for j in range(i, M + 1, i): if j in s: gcd = math.gcd(gcd, j) # Store the value i in Ans[] # if it can be the GCD if gcd == i: Ans += [i] # Print all possible GCDs stored print(*Ans) # Driver Code N = 7 arr = [3, 4, 8] # Function Call findGCDsSubsequence(arr)
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ static int gcd1(int a, int b) { return b == 0 ? a : gcd1(b, a % b); } // Function to find the different GCDs of // the subsequence of the given array static void findGCDsSubsequence(List<int> arr) { // Stores all the possible GCDs List<int> ans = new List<int>(); // Stores all array element in set HashSet<int> s = new HashSet<int>(); foreach(int i in arr) s.Add(i); int M = Int32.MinValue; foreach(int i in arr) { if (i > M) M = i; } // Iterate over the range [1, M] for(int i = 1; i <= M; i++) { int gcd = 0; // Check if i can be the GCD of // any subsequence for(int j = i; j < M + 1; j += i) { if (s.Contains(j)) gcd = gcd1(gcd, j); } if (gcd == i) ans.Add(i); } for(int i = 0; i < ans.Count; i++) Console.Write(ans[i] + " "); } // Driver Code public static void Main() { List<int> arr = new List<int>(){ 3, 4, 8 }; // Function Call findGCDsSubsequence(arr); } } // This code is contributed by SURENDRA_GANGWAR
Javascript
<script> // JavaScript program for the above approach function __gcd(a, b) { if (b == 0) return a; return __gcd(b, a % b); } // Function to find the different GCDs of // the subsequence of the given array function findGCDsSubsequence(arr) { // Stores all the possible GCDs let ans = []; // Stores all array element in set let s = new Set(); for (let i of arr) s.add(i); let M = [...arr].sort((a, b) => b - a)[0] // Iterate over the range [1, M] for (let i = 1; i <= M; i++) { let gcd = 0; // Check if i can be the GCD of // any subsequence for (let j = i; j < M + 1; j += i) { if (s.has(j)) gcd = __gcd(gcd, j); } if (gcd == i) ans.push(i); } for (let i = 0; i < ans.length; i++) document.write(ans[i] + " "); } // Driver Code let N = 7; let arr = [3, 4, 8]; // Function Call findGCDsSubsequence(arr); // This code is contributed by gfgking </script>
1 3 4 8
Complejidad temporal: O(M*log M), donde M es el elemento máximo del arreglo .
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por parthagarwal1962000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA