Dada una array arr[] de números positivos. La tarea es verificar si existe algún subconjunto de cualquier tamaño tal que después de multiplicar cada elemento del subconjunto con cualquier número entero, dará la suma del subconjunto como 1.
Ejemplos:
Entrada: arr[] = {12, 5, 9, 21}
Salida: Verdadero
Explicación: Elija los números 5 y 9. 5*2 + 9*(-1) = 1Entrada: arr[] = {9, 29, 6, 10}
Salida: Verdadero
Explicación: Elija los números 29 y 10. 29*(-1) + 10*(3) = 1
Enfoque: si el HCF de cualquier par de números de la array es 1 , devuelva True else False . La ecuación ax + by = 1 tiene solución para xey si mcd(a, b) = 1 . No es necesario verificar el HCF de todos los pares posibles porque GCD es una función asociativa.
mcd(a0, a1, …, an – 1) = mcd(a0, mcd(a1, …, an-1) = mcd(mcd(a0, a1), mcd(a2, …, an-1)) = …
y así sucesivamente, se incluyen todas las combinaciones posibles. Así que simplemente itere a través de la array hasta que se encuentre un gcd de 1 . En otro mundo, si mcd(a0, a1, …, an – 1) = 1, existe una subsecuencia aij con #{ai0, …, aik} = k, 1 <= k <= N , que da un mcd de 1 . Siga los pasos a continuación para resolver el problema:
- Inicialice la variable res como arr[0].
- Itere sobre el rango [1, N) usando la variable i y realice las siguientes tareas:
- Establezca el valor de res como el gcd de res y arr[i].
- Si res es igual a 1, devuelve verdadero.
- Después de realizar los pasos anteriores, escriba falso como respuesta.
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 find GCD int gcd(int a, int b) { if (a < b) gcd(b, a); if (a % b == 0) return b; else return gcd(b, a % b); } // Utility Function bool IsArrayGood(int arr[], int N) { int i, res = arr[0]; for (i = 1; i < N; i++) { res = gcd(res, arr[i]); if (res == 1) return true; } return false; } // Driver Code int main() { int arr[] = { 12, 5, 9, 21 }; int N = sizeof(arr) / sizeof(arr[0]); bool ver = IsArrayGood(arr, N); if (ver == true) cout << "True"; else cout << "False"; return 0; }
Java
/*package whatever //do not write package name here */ import java.io.*; import java.lang.*; import java.util.*; public class GFG { // Recursive function to return gcd of a and b static int gcd(int a, int b) { if (a < b) gcd(b, a); if (a % b == 0) return b; else return gcd(b, a % b); } // Utility Function static boolean IsArrayGood(int arr[], int N) { int i, res = arr[0]; for (i = 1; i < N; i++) { res = gcd(res, arr[i]); if (res == 1) return true; } return false; } // Driver Code public static void main(String[] args) { int arr[] = { 12, 5, 9, 21 }; int N = arr.length; boolean ver = IsArrayGood(arr, N); if (ver == true){ System.out.println("True"); } else{ System.out.println("False"); } } } // This code is contributed by hrithikgarg03188
Python3
# Python code for the above approach # Function to find GCD def gcd(a, b): if (a < b): gcd(b, a); if (a % b == 0): return b; else: return gcd(b, a % b); # Utility Function def IsArrayGood(arr, N): i = None res = arr[0]; for i in range(1, N): res = gcd(res, arr[i]); if (res == 1): return True; return False; # Driver Code arr = [12, 5, 9, 21]; N = len(arr) ver = IsArrayGood(arr, N); if (ver == True): print("True"); else: print("False"); # This code is contributed by Saurabh Jaiswal
C#
/*package whatever //do not write package name here */ using System; public class GFG { // Recursive function to return gcd of a and b static int gcd(int a, int b) { if (a < b) gcd(b, a); if (a % b == 0) return b; else return gcd(b, a % b); } // Utility Function static bool IsArrayGood(int[] arr, int N) { int i, res = arr[0]; for (i = 1; i < N; i++) { res = gcd(res, arr[i]); if (res == 1) return true; } return false; } // Driver Code public static void Main() { int[] arr = { 12, 5, 9, 21 }; int N = arr.Length; bool ver = IsArrayGood(arr, N); if (ver == true){ Console.Write("True"); } else{ Console.Write("False"); } } } // This code is contributed by gfgking
Javascript
<script> // JavaScript code for the above approach // Function to find GCD function gcd(a, b) { if (a < b) gcd(b, a); if (a % b == 0) return b; else return gcd(b, a % b); } // Utility Function function IsArrayGood(arr, N) { let i, res = arr[0]; for (i = 1; i < N; i++) { res = gcd(res, arr[i]); if (res == 1) return true; } return false; } // Driver Code let arr = [12, 5, 9, 21]; let N = arr.length; let ver = IsArrayGood(arr, N); if (ver == true) document.write("True"); else document.write("False"); // This code is contributed by Potta Lokesh </script>
True
Complejidad de tiempo: O(N*log(D)) donde D es el elemento máximo en el arreglo
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pintusaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA