Dados n enteros, necesitamos encontrar el tamaño del subconjunto más grande con GCD igual a 1.
Restricción de entrada:
n <= 10^5 A[i] <= 10^5
Ejemplos:
Input : A = {2, 3, 5}
Output : 3
Input : A = {3, 18, 12}
Output : -1
Solución ingenua:
Encontramos GCD de todos los subconjuntos posibles y encontramos el subconjunto más grande cuyo GCD es 1. El tiempo total tomado será igual al tiempo tomado para evaluar el GCD de todos los subconjuntos posibles. Los subconjuntos posibles totales son 2 n . En el peor de los casos, hay n elementos en el subconjunto y el tiempo necesario para calcular su GCD será n * log(n) El
espacio adicional necesario para contener el subconjunto actual es O(n)
Time complexity : O(n * log(n) * 2^n) Space Complexity : O(n)
Solución O(n) optimizada:
Digamos que encontramos un subconjunto con GCD 1, si le agregamos un nuevo elemento, entonces GCD sigue siendo 1. Por lo tanto, si existe un subconjunto con GCD 1, entonces GCD del conjunto completo también es 1. Por lo tanto, primero encontramos GCD del conjunto completo conjunto, si es 1, entonces el conjunto completo es ese subconjunto; de lo contrario, no existe ningún subconjunto con GCD 1.
C++
// C++ program to find size of the largest subset with GCD 1
#include <iostream>
using namespace std;
// Function to return gcd of a and b
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b%a, a);
}
// Function to find largest subset with GCD 1
int largestGCD1Subset(int A[], int n)
{
// finding gcd of whole array
int currentGCD = A[0];
for (int i=1; i<n; i++)
{
currentGCD = gcd(currentGCD, A[i]);
// If current GCD becomes 1 at any moment,
// then whole array has GCD 1.
if (currentGCD == 1)
return n;
}
return 0;
}
// Driver program to test above function
int main()
{
int A[] = {2, 18, 6, 3};
int n = sizeof(A)/sizeof(A[0]);
cout << largestGCD1Subset(A, n);
return 0;
}
Java
// Java program to find size of the
// largest subset with GCD 1
import java.*;
class GFG {
// Function to return gcd of
// a and b
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to find largest
// subset with GCD 1
static int largestGCD1Subset(int A[],
int n)
{
// finding gcd of whole array
int currentGCD = A[0];
for (int i=1; i<n; i++)
{
currentGCD =
gcd(currentGCD, A[i]);
// If current GCD becomes 1
// at any moment, then whole
// array has GCD 1.
if (currentGCD == 1)
return n;
}
return 0;
}
// Driver code
public static void main (String[] args)
{
int A[] = {2, 18, 6, 3};
int n =A.length;
System.out.println(
largestGCD1Subset(A, n) );
}
}
// This code is contributed by Sam007.
Python3
# python program to find size of the # largest subset with GCD 1 # Function to return gcd of a and b def gcd( a, b): if (a == 0): return b return gcd(b%a, a) # Function to find largest subset # with GCD 1 def largestGCD1Subset(A, n): # finding gcd of whole array currentGCD = A[0]; for i in range(1, n): currentGCD = gcd(currentGCD, A[i]) # If current GCD becomes 1 at # any moment, then whole # array has GCD 1. if (currentGCD == 1): return n return 0 # Driver code A = [2, 18, 6, 3] n = len(A) print (largestGCD1Subset(A, n)) # This code is Contributed by Sam007.
C#
// C# program to find size of the
// largest subset with GCD 1
using System;
public class GFG {
// Function to return gcd of
// a and b
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to find largest subset
// with GCD 1
static int largestGCD1Subset(int []A,
int n)
{
// finding gcd of whole array
int currentGCD = A[0];
for (int i = 1; i < n; i++)
{
currentGCD =
gcd(currentGCD, A[i]);
// If current GCD becomes 1 at
// any moment, then whole
// array has GCD 1.
if (currentGCD == 1)
return n;
}
return 0;
}
// Driver method
public static void Main()
{
int []A = {2, 18, 6, 3};
int n = A.Length;
Console.Write(
largestGCD1Subset(A, n));
}
}
// This code is contributed by Sam007.
PHP
<?php
// php program to find size of the
// largest subset with GCD 1
// Function to return gcd of a and b
function gcd($a, $b)
{
if ($a == 0)
return $b;
return gcd($b % $a, $a);
}
// Function to find largest subset
// with GCD 1
function largestGCD1Subset($A, $n)
{
// finding gcd of whole array
$currentGCD = $A[0];
for ( $i = 1; $i < $n; $i++)
{
$currentGCD =
gcd($currentGCD, $A[$i]);
// If current GCD becomes 1
// at any moment, then
// whole array has GCD 1.
if ($currentGCD == 1)
return $n;
}
return 0;
}
// Driver program
$A = array(2, 18, 6, 3);
$n = sizeof($A);
echo largestGCD1Subset($A, $n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find size of the
// largest subset with GCD 1
// Function to return gcd of a and b
function gcd(a, b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to find largest subset
// with GCD 1
function largestGCD1Subset(A, n)
{
// finding gcd of whole array
let currentGCD = A[0];
for ( let i = 1; i < n; i++)
{
currentGCD =
gcd(currentGCD, A[i]);
// If current GCD becomes 1
// at any moment, then
// whole array has GCD 1.
if (currentGCD == 1)
return n;
}
return 0;
}
// Driver program
let A = [2, 18, 6, 3];
let n = A.length;
document.write(largestGCD1Subset(A, n));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
4
Time Complexity : O(n* log(n)) Space Complexity : O(1)
Este artículo es una contribución de Pratik Chhajer . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA