Dada una array A de tamaño N, nuestra tarea es encontrar la longitud del subconjunto más grande de modo que todos los elementos del subconjunto sean coprimos por pares , es decir, para dos elementos x e y donde x e y no son iguales, el mcd ( x, y) es igual a 1 .
Nota: Todos los elementos de la array son <= 50.
Ejemplos:
Entrada: A = [2, 5, 2, 5, 2]
Salida: 2
Explicación:
El subconjunto más grande que satisface la condición es: {2, 5}Entrada: A = [2, 3, 13, 5, 14, 6, 7, 11]
Salida: 6
Enfoque ingenuo:
para resolver el problema mencionado anteriormente, debemos generar todos los subconjuntos y, para cada subconjunto, verificar si la condición dada se cumple o no. Pero este método requiere un tiempo O(N 2 * 2 N ) y se puede optimizar aún más.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Find the length of the Largest
// subset such that all elements are Pairwise Coprime
#include <bits/stdc++.h>
using namespace std;
// Function to find the largest subset possible
int largestSubset(int a[], int n)
{
int answer = 0;
// Iterate through all the subsets
for (int i = 1; i < (1 << n); i++) {
vector<int> subset;
/* Check if jth bit in the counter is set */
for (int j = 0; j < n; j++) {
if (i & (1 << j))
subset.push_back(a[j]);
}
bool flag = true;
for (int j = 0; j < subset.size(); j++) {
for (int k = j + 1; k < subset.size(); k++) {
// Check if the gcd is not equal to 1
if (__gcd(subset[j], subset[k]) != 1)
flag = false;
}
}
if (flag == true)
// Update the answer with maximum value
answer = max(answer, (int)subset.size());
}
// Return the final result
return answer;
}
// Driver code
int main()
{
int A[] = { 2, 3, 13, 5, 14, 6, 7, 11 };
int N = sizeof(A) / sizeof(A[0]);
cout << largestSubset(A, N);
return 0;
}
Java
// Java implementation to find the length
// of the largest subset such that all
// elements are Pairwise Coprime
import java.util.*;
class GFG{
static int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// Base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a - b, b);
return gcd(a, b - a);
}
// Function to find the largest subset possible
static int largestSubset(int a[], int n)
{
int answer = 0;
// Iterate through all the subsets
for(int i = 1; i < (1 << n); i++)
{
Vector<Integer> subset = new Vector<Integer>();
// Check if jth bit in the counter is set
for(int j = 0; j < n; j++)
{
if ((i & (1 << j)) != 0)
subset.add(a[j]);
}
boolean flag = true;
for(int j = 0; j < subset.size(); j++)
{
for(int k = j + 1; k < subset.size(); k++)
{
// Check if the gcd is not equal to 1
if (gcd((int)subset.get(j),
(int) subset.get(k)) != 1)
flag = false;
}
}
if (flag == true)
// Update the answer with maximum value
answer = Math.max(answer,
(int)subset.size());
}
// Return the final result
return answer;
}
// Driver code
public static void main(String args[])
{
int A[] = { 2, 3, 13, 5, 14, 6, 7, 11 };
int N = A.length;
System.out.println(largestSubset(A, N));
}
}
// This code is contributed by Stream_Cipher
Python3
# Python3 implementation to Find # the length of the Largest subset # such that all elements are Pairwise Coprime import math # Function to find the largest subset possible def largestSubset(a, n): answer = 0 # Iterate through all the subsets for i in range(1, (1 << n)): subset = [] # Check if jth bit in the counter is set for j in range(0, n): if (i & (1 << j)): subset.insert(j, a[j]) flag = True for j in range(0, len(subset)): for k in range(j + 1, len(subset)): # Check if the gcd is not equal to 1 if (math.gcd(subset[j], subset[k]) != 1) : flag = False if (flag == True): # Update the answer with maximum value answer = max(answer, len(subset)) # Return the final result return answer # Driver code A = [ 2, 3, 13, 5, 14, 6, 7, 11 ] N = len(A) print(largestSubset(A, N)) # This code is contributed by Sanjit_Prasad
C#
// C# implementation to Find the length
// of the largest subset such that all
// elements are Pairwise Coprime
using System;
using System.Collections.Generic;
class GFG{
static int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a - b, b);
return gcd(a, b - a);
}
// Function to find the largest subset possible
static int largestSubset(int []a, int n)
{
int answer = 0;
// Iterate through all the subsets
for(int i = 1; i < (1 << n); i++)
{
List<int> subset = new List<int>();
// Check if jth bit in the counter is set
for(int j = 0; j < n; j++)
{
if ((i & (1 << j)) != 0)
subset.Add(a[j]);
}
int flag = 1;
for(int j = 0; j < subset.Count; j++)
{
for(int k = j + 1; k < subset.Count; k++)
{
// Check if the gcd is not equal to 1
if (gcd((int)subset[j],
(int) subset[k]) != 1)
flag = 0;
}
}
if (flag == 1)
// Update the answer with maximum value
answer = Math.Max(answer,
(int)subset.Count);
}
// Return the final result
return answer;
}
// Driver code
public static void Main()
{
int []A = { 2, 3, 13, 5, 14, 6, 7, 11 };
int N = A.Length;
Console.WriteLine(largestSubset(A, N));
}
}
// This code is contributed by Stream_Cipher
Javascript
<script>
// Javascript implementation to Find the length
// of the largest subset such that all
// elements are Pairwise Coprime
function gcd(a, b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a - b, b);
return gcd(a, b - a);
}
// Function to find the largest subset possible
function largestSubset(a, n)
{
let answer = 0;
// Iterate through all the subsets
for(let i = 1; i < (1 << n); i++)
{
let subset = [];
// Check if jth bit in the counter is set
for(let j = 0; j < n; j++)
{
if ((i & (1 << j)) != 0)
subset.push(a[j]);
}
let flag = 1;
for(let j = 0; j < subset.length; j++)
{
for(let k = j + 1; k < subset.length; k++)
{
// Check if the gcd is not equal to 1
if (gcd(subset[j], subset[k]) != 1)
flag = 0;
}
}
if (flag == 1)
// Update the answer with maximum value
answer = Math.max(answer, subset.length);
}
// Return the final result
return answer;
}
let A = [ 2, 3, 13, 5, 14, 6, 7, 11 ];
let N = A.length;
document.write(largestSubset(A, N));
</script>
Producción:
6
Enfoque eficiente:
el método anterior se puede optimizar y el enfoque depende del hecho de que solo hay 15 números primos en los primeros 50 números naturales. Entonces, todos los números en la array tendrán factores primos solo entre estos 15 números. Usaremos Bitmasking y Programación Dinámica para optimizar el problema.
- Dado que solo hay 15 números primos, considere una representación de 15 bits de cada número donde cada bit es 1 si ese índice de números primos es un factor de ese número. Indexaremos los números primos por indexación 0, lo que significa 2 en la posición 0, 3 en el índice 1 y así sucesivamente.
- Una variable entera ‘ máscara ‘ indica los factores primos que ya han ocurrido en el subconjunto. Si se establece el i-ésimo bit en la máscara, entonces se ha producido el i-ésimo factor primo, de lo contrario no.
- En cada paso de la relación de recurrencia , el elemento puede incluirse en el subconjunto o no puede incluirse. Si el elemento no está incluido en el subarreglo, simplemente muévase al siguiente índice. Si está incluido, cambie la máscara poniendo en ON todos los bits correspondientes a los factores primos del elemento actual en la máscara. El elemento actual solo se puede incluir si todos sus factores primos no han ocurrido previamente.
- Esta condición se cumplirá solo si los bits correspondientes a los dígitos del elemento actual en la máscara están en OFF.
Si dibujamos el árbol de recursión completo, podemos observar que se están resolviendo muchos subproblemas que ocurrían una y otra vez. Así que usamos una tabla dp[][] tal que para cada índice dp[i][j], i es la posición del elemento en la array y j es la máscara.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Find the length of the Largest
// subset such that all elements are Pairwise Coprime
#include <bits/stdc++.h>
using namespace std;
// Dynamic programming table
int dp[5000][(1 << 10) + 5];
// Function to obtain the mask for any integer
int getmask(int val)
{
int mask = 0;
// List of prime numbers till 50
int prime[15] = { 2, 3, 5, 7, 11, 13, 17, 19,
23, 29, 31, 37, 41, 43, 47 };
// Iterate through all prime numbers to obtain the mask
for (int i = 0; i < 15; i++) {
if (val % prime[i] == 0) {
// Set this prime's bit ON in the mask
mask = mask | (1 << i);
}
}
// Return the mask value
return mask;
}
// Function to count the number of ways
int calculate(int pos, int mask,
int a[], int n)
{
if (pos == n || mask == (1 << n - 1))
return 0;
// Check if subproblem has been solved
if (dp[pos][mask] != -1)
return dp[pos][mask];
int size = 0;
// Excluding current element in the subset
size = max(size, calculate(pos + 1, mask, a, n));
// Check if there are no common prime factors
// then only this element can be included
if ((getmask(a[pos]) & mask) == 0) {
// Calculate the new mask if this element is included
int new_mask = (mask | (getmask(a[pos])));
size = max(size, 1 + calculate(pos + 1, new_mask, a, n));
}
// Store and return the answer
return dp[pos][mask] = size;
}
// Function to find the count of
// subarray with all digits unique
int largestSubset(int a[], int n)
{
// Initializing dp
memset(dp, -1, sizeof(dp));
return calculate(0, 0, a, n);
}
// Driver code
int main()
{
int A[] = { 2, 3, 13, 5, 14, 6, 7, 11 };
int N = sizeof(A) / sizeof(A[0]);
cout << largestSubset(A, N);
return 0;
}
Java
// Java implementation to find the length
// of the largest subset such that all
// elements are Pairwise Coprime
import java.util.*;
class GFG{
// Dynamic programming table
static int dp[][] = new int [5000][1029];
// Function to obtain the mask for any integer
static int getmask(int val)
{
int mask = 0;
// List of prime numbers till 50
int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19,
23, 29, 31, 37, 41, 43, 47 };
// Iterate through all prime numbers
// to obtain the mask
for(int i = 0; i < 15; i++)
{
if (val % prime[i] == 0)
{
// Set this prime's bit ON in the mask
mask = mask | (1 << i);
}
}
// Return the mask value
return mask;
}
// Function to count the number of ways
static int calculate(int pos, int mask,
int a[], int n)
{
if (pos == n ||
mask == (int)(1 << n - 1))
return 0;
// Check if subproblem has been solved
if (dp[pos][mask] != -1)
return dp[pos][mask];
int size = 0;
// Excluding current element in the subset
size = Math.max(size, calculate(pos + 1,
mask, a, n));
// Check if there are no common prime factors
// then only this element can be included
if ((getmask(a[pos]) & mask) == 0)
{
// Calculate the new mask if this
// element is included
int new_mask = (mask | (getmask(a[pos])));
size = Math.max(size, 1 + calculate(pos + 1,
new_mask,
a, n));
}
// Store and return the answer
return dp[pos][mask] = size;
}
// Function to find the count of
// subarray with all digits unique
static int largestSubset(int a[], int n)
{
for(int i = 0; i < 5000; i++)
Arrays.fill(dp[i], -1);
return calculate(0, 0, a, n);
}
// Driver code
public static void main(String args[])
{
int A[] = { 2, 3, 13, 5, 14, 6, 7, 11 };
int N = A.length;
System.out.println(largestSubset(A, N));
}
}
// This code is contributed by Stream_Cipher
Python
# Python implementation to find the # length of the Largest subset such # that all elements are Pairwise Coprime # Dynamic programming table dp = [[-1] * ((1 << 10) + 5)] * 5000 # Function to obtain the mask for any integer def getmask(val): mask = 0 # List of prime numbers till 50 prime = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 ] # Iterate through all prime numbers # to obtain the mask for i in range(1, 15): if val % prime[i] == 0: # Set this prime's bit ON in the mask mask = mask | (1 << i) # Return the mask value return mask # Function to count the number of ways def calculate(pos, mask, a, n): if ((pos == n) or (mask == (1 << n - 1))): return 0 # Check if subproblem has been solved if dp[pos][mask] != -1: return dp[pos][mask] size = 0 # Excluding current element in the subset size = max(size, calculate(pos + 1, mask, a, n)) # Check if there are no common prime factors # then only this element can be included if (getmask(a[pos]) & mask) == 0: # Calculate the new mask if this # element is included new_mask = (mask | (getmask(a[pos]))) size = max(size, 1 + calculate(pos + 1, new_mask, a, n)) # Store and return the answer dp[pos][mask] = size return dp[pos][mask] # Function to find the count of # subarray with all digits unique def largestSubset(A, n): return calculate(0, 0, A, n); # Driver code A = [ 2, 3, 13, 5, 14, 6, 7, 11 ] N = len(A) print(largestSubset(A, N)) # This code is contributed by Stream_Cipher
C#
// C# implementation to find the length
// of the largest subset such that all
// elements are Pairwise Coprime
using System;
class GFG{
// Dynamic programming table
static int [,] dp = new int [5000, 1029];
// Function to obtain the mask for any integer
static int getmask(int val)
{
int mask = 0;
// List of prime numbers till 50
int []prime = { 2, 3, 5, 7, 11, 13, 17, 19,
23, 29, 31, 37, 41, 43, 47 };
// Iterate through all prime
// numbers to obtain the mask
for(int i = 0; i < 15; i++)
{
if (val % prime[i] == 0)
{
// Set this prime's bit ON in the mask
mask = mask | (1 << i);
}
}
// Return the mask value
return mask;
}
// Function to count the number of ways
static int calculate(int pos, int mask,
int []a, int n)
{
if (pos == n ||
mask == (int)(1 << n - 1))
return 0;
// Check if subproblem has been solved
if (dp[pos, mask] != -1)
return dp[pos, mask];
int size = 0;
// Excluding current element in the subset
size = Math.Max(size, calculate(pos + 1,
mask, a, n));
// Check if there are no common prime factors
// then only this element can be included
if ((getmask(a[pos]) & mask) == 0)
{
// Calculate the new mask if
// this element is included
int new_mask = (mask | (getmask(a[pos])));
size = Math.Max(size, 1 + calculate(pos + 1,
new_mask,
a, n));
}
// Store and return the answer
return dp[pos, mask] = size;
}
// Function to find the count of
// subarray with all digits unique
static int largestSubset(int []a, int n)
{
for(int i = 0; i < 5000; i++)
{
for(int j = 0; j < 1029; j++)
dp[i, j] = -1;
}
return calculate(0, 0, a, n);
}
// Driver code
public static void Main()
{
int []A = { 2, 3, 13, 5, 14, 6, 7, 11 };
int N = A.Length;
Console.WriteLine(largestSubset(A, N));
}
}
// This code is contributed by Stream_Cipher
Javascript
<script>
// JavaScript implementation to
// Find the length of the Largest
// subset such that all elements
// are Pairwise Coprime
// Dynamic programming table
var dp = Array.from(Array(5000), ()=>Array((1 << 10) + 5));
// Function to obtain the mask for any integer
function getmask( val)
{
var mask = 0;
// List of prime numbers till 50
var prime = [2, 3, 5, 7, 11, 13, 17, 19,
23, 29, 31, 37, 41, 43, 47];
// Iterate through all prime numbers to obtain the mask
for (var i = 0; i < 15; i++) {
if (val % prime[i] == 0) {
// Set this prime's bit ON in the mask
mask = mask | (1 << i);
}
}
// Return the mask value
return mask;
}
// Function to count the number of ways
function calculate(pos, mask, a, n)
{
if (pos == n || mask == (1 << n - 1))
return 0;
// Check if subproblem has been solved
if (dp[pos][mask] != -1)
return dp[pos][mask];
var size = 0;
// Excluding current element in the subset
size = Math.max(size, calculate(pos + 1, mask, a, n));
// Check if there are no common prime factors
// then only this element can be included
if ((getmask(a[pos]) & mask) == 0) {
// Calculate the new mask if this element is included
var new_mask = (mask | (getmask(a[pos])));
size = Math.max(size,
1 + calculate(pos + 1, new_mask, a, n));
}
// Store and return the answer
return dp[pos][mask] = size;
}
// Function to find the count of
// subarray with all digits unique
function largestSubset(a, n)
{
// Initializing dp
dp = Array.from(Array(5000),
()=>Array((1 << 10) + 5).fill(-1));
return calculate(0, 0, a, n);
}
// Driver code
var A = [2, 3, 13, 5, 14, 6, 7, 11 ];
var N = A.length;
document.write( largestSubset(A, N));
</script>
Producción:
6
Complejidad de tiempo: O(N * 15 * 2 15 )