Dada una array arr[] de N enteros positivos. La tarea es encontrar la longitud de la subsecuencia más corta tal que el GCD de la subsecuencia sea 1. Si ninguna de las subsecuencias tiene GCD 1, imprima «-1 «.
Ejemplos:
Entrada: arr[] = {2, 6, 12, 3}
Salida: 2
Explicación:
El GCD de 2, 3 = 1, que es la longitud más pequeña de la subsecuencia como 2.Entrada: arr[] = {2, 4}
Salida: -1
Explicación:
GCD de 2, 4 = 2
Enfoque ingenuo: la idea es generar todas las subsecuencias posibles de la array dada e imprimir la longitud de esa subsecuencia cuyo GCD es la unidad y tiene una longitud mínima. Si ninguna de las subsecuencias tiene GCD 1, imprima «-1 «.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: hay 2 observaciones clave para resolver este problema:
- Dos números tendrán su MCD igual a uno solo cuando sus factores primos sean diferentes.
- Cualquier número positivo que sea menor que 10 9 puede tener un máximo de 9 factores primos.
Por Ejemplo 2×3×5×7×11×13×17×19×23 = 22, 30, 92, 870. Si multiplicamos este número por el siguiente número primo, que es 29, será mayor que 10^ 9.
Siga los pasos a continuación para resolver el problema:
- Expresar los números como el producto de sus factores primos . Como tenemos un máximo de 9 factores primos , podemos usar el concepto de máscara de bits para almacenar el estado del número.
Por ejemplo , los factores primos de 12 son 2 y 3. Esto se puede expresar en binario como 11 (ignorando los ceros anteriores), lo que significa que hay dos factores primos para este número. - Para cada número en la array de entrada, verifique si algún otro número tiene el bit correspondiente establecido o no. Esto podría lograrse utilizando la operación AND bit a bit . La resultante de esta operación es otro estado de nuestro espacio de solución.
- Ahora usa el concepto de Programación Dinámica para memorizar los estados. La idea es usar una array para almacenar los estados del espacio de solución. Esto funciona ya que solo se pueden configurar 9 bits a la vez, y una array de tamaño 1024 podría capturar todos los estados del espacio de la solución.
- Cada estado utiliza programación dinámica para almacenar el camino más corto para llegar a ese estado.
- Si el AND bit a bit de cualquiera de los dos estados es igual a 0 , entonces el GCD es igual a uno , es decir, si existe la posibilidad de alcanzar el estado 0 desde el estado actual, entonces tendrá la subsecuencia de longitud mínima e imprimirá eso. longitud de lo contrario imprime «-1» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that finds the prime
// factors of a number
vector<int> findPrimeFactors(int n)
{
// To store the prime factor
vector<int> primeFactors(9, 0);
int j = 0;
// 2s that divide n
if (n % 2 == 0) {
primeFactors[j++] = 2;
while (n % 2 == 0)
n >>= 1;
}
// N must be odd at this point
// Skip one element
for (int i = 3;
i * i <= n; i += 2) {
if (n % i == 0) {
// Update the prime factor
primeFactors[j++] = i;
while (n % i == 0)
n /= i;
}
}
// If n is a prime number
// greater than 2
if (n > 2)
primeFactors[j++] = n;
vector<int> PrimeFactors(j);
for(int i = 0; i < j; i++)
{
PrimeFactors[i] = primeFactors[i];
}
return PrimeFactors;
}
// Function that finds the shortest
// subsequence
void findShortestSubsequence(vector<int> &dp, vector<int> a,
int index, vector<int> primeFactors)
{
int n = a.size();
for (int j = index; j < n; j++) {
int bitmask = 0;
for (int p = 0;
p < primeFactors.size(); p++) {
// Check if the prime factor
// of first number, is also
// the prime factor of the
// rest numbers in array
if ((a[j] % primeFactors[p]) == 0) {
// Set corresponding bit
// of prime factor to 1,
// it means both these
// numbers have the
// same prime factor
bitmask ^= (1 << p);
}
}
for (int i = 0; i < dp.size(); i++) {
// If no states encountered
// so far continue for this
// combination of bits
if (dp[i] == n + 1)
continue;
// Update this state with
// minimum ways to reach
// this state
dp[bitmask & i]
= min(dp[bitmask & i],
dp[i] + 1);
}
}
}
// Function that print the minimum
// length of subsequence
void printMinimumLength(vector<int> a)
{
int Min = a.size() + 1;
for (int i = 0; i < a.size() - 1; i++) {
// Find the prime factors of
// the first number
vector<int> primeFactors
= findPrimeFactors(a[i]);
int n = primeFactors.size();
// Initialize the array with
// maximum steps, size of the
// array + 1 for instance
vector<int> dp(1 << n, a.size() + 1);
// Express the prime factors
// in bit representation
// Total number of set bits is
// equal to the total number
// of prime factors
int setBits = (1 << n) - 1;
// Indicates there is one
// way to reach the number
// under consideration
dp[setBits] = 1;
findShortestSubsequence(dp, a, i + 1,
primeFactors);
// State 0 corresponds
// to gcd of 1
Min = min(dp[0], Min);
}
// If not found such subsequence
// then print "-1"
if (Min == (a.size() + 1))
cout << -1 << endl;
// Else print the length
else
cout << Min << endl;
}
// Driver code
int main()
{
// Given array arr[]
vector<int> arr = { 2, 6, 12, 3 };
// Function Call
printMinimumLength(arr);
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function that finds the prime
// factors of a number
private static int[] findPrimeFactors(int n)
{
// To store the prime factor
int[] primeFactors = new int[9];
int j = 0;
// 2s that divide n
if (n % 2 == 0) {
primeFactors[j++] = 2;
while (n % 2 == 0)
n >>= 1;
}
// N must be odd at this point
// Skip one element
for (int i = 3;
i * i <= n; i += 2) {
if (n % i == 0) {
// Update the prime factor
primeFactors[j++] = i;
while (n % i == 0)
n /= i;
}
}
// If n is a prime number
// greater than 2
if (n > 2)
primeFactors[j++] = n;
return Arrays.copyOfRange(primeFactors, 0, j);
}
// Function that finds the shortest
// subsequence
private static void
findShortestSubsequence(int[] dp, int[] a,
int index,
int[] primeFactors)
{
int n = a.length;
for (int j = index; j < n; j++) {
int bitmask = 0;
for (int p = 0;
p < primeFactors.length; p++) {
// Check if the prime factor
// of first number, is also
// the prime factor of the
// rest numbers in array
if (a[j] % primeFactors[p] == 0) {
// Set corresponding bit
// of prime factor to 1,
// it means both these
// numbers have the
// same prime factor
bitmask ^= (1 << p);
}
}
for (int i = 0;
i < dp.length; i++) {
// If no states encountered
// so far continue for this
// combination of bits
if (dp[i] == n + 1)
continue;
// Update this state with
// minimum ways to reach
// this state
dp[bitmask & i]
= Math.min(dp[bitmask & i],
dp[i] + 1);
}
}
}
// Function that print the minimum
// length of subsequence
private static void
printMinimumLength(int[] a)
{
int min = a.length + 1;
for (int i = 0;
i < a.length - 1; i++) {
// Find the prime factors of
// the first number
int[] primeFactors
= findPrimeFactors(a[i]);
int n = primeFactors.length;
int[] dp = new int[1 << n];
// Initialize the array with
// maximum steps, size of the
// array + 1 for instance
Arrays.fill(dp, a.length + 1);
// Express the prime factors
// in bit representation
// Total number of set bits is
// equal to the total number
// of prime factors
int setBits = (1 << n) - 1;
// Indicates there is one
// way to reach the number
// under consideration
dp[setBits] = 1;
findShortestSubsequence(dp, a, i + 1,
primeFactors);
// State 0 corresponds
// to gcd of 1
min = Math.min(dp[0], min);
}
// If not found such subsequence
// then print "-1"
if (min == a.length + 1)
System.out.println(-1);
// Else print the length
else
System.out.println(min);
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int[] arr = { 2, 6, 12, 3 };
// Function Call
printMinimumLength(arr);
}
}
Python3
# Python3 program for the above approach # Function that finds the prime # factors of a number def findPrimeFactors(n): # To store the prime factor primeFactors = [0 for i in range(9)] j = 0 # 2s that divide n if (n % 2 == 0): primeFactors[j] = 2 j += 1 while (n % 2 == 0): n >>= 1 # N must be odd at this point # Skip one element i = 3 while (i * i <= n): if (n % i == 0): # Update the prime factor primeFactors[j] = i j += 1 while(n % i == 0): n //= i i += 2 # If n is a prime number # greater than 2 if (n > 2): primeFactors[j] = n j += 1 for i in range(0, j + 1): primeFactors[i] = 0 return primeFactors # Function that finds the shortest # subsequence def findShortestSubsequence(dp, a, index, primeFactors): n = len(a) for j in range(index, n): bitmask = 0 for p in range(len(primeFactors)): # Check if the prime factor # of first number, is also # the prime factor of the # rest numbers in array if (primeFactors[p] != 0 and a[j] % primeFactors[p] == 0): # Set corresponding bit # of prime factor to 1, # it means both these # numbers have the # same prime factor bitmask ^= (1 << p) for i in range(len(dp)): # If no states encountered # so far continue for this # combination of bits if (dp[i] == n + 1): continue # Update this state with # minimum ways to reach # this state dp[bitmask & i] = min(dp[bitmask & i], dp[i] + 1) # Function that print the minimum # length of subsequence def printMinimumLength(a): mn = len(a) + 1 for i in range(len(a) - 1): # Find the prime factors of # the first number primeFactors = findPrimeFactors(a[i]) n = len(primeFactors) dp = [0 for i in range(1 << n)] # Initialize the array with # maximum steps, size of the # array + 1 for instance dp = [len(a) + 1 for i in range(len(dp))] # Express the prime factors # in bit representation # Total number of set bits is # equal to the total number # of prime factors setBits = (1 << n) - 1 # Indicates there is one # way to reach the number # under consideration dp[setBits] = 1 findShortestSubsequence(dp, a, i + 1, primeFactors) # State 0 corresponds # to gcd of 1 mn = min(dp[0], mn) # If not found such subsequence # then print "-1" if (mn == len(a) + 1): print(-1) # Else print the length else: print(mn) # Driver Code if __name__ == '__main__': # Given array arr[] arr = [ 2, 6, 12, 3 ] # Function Call printMinimumLength(arr) # This code is contributed by bgangwar59
C#
// C# program for
// the above approach
using System;
class GFG{
// Function that finds the prime
// factors of a number
private static int[] findPrimeFactors(int n)
{
// To store the prime factor
int[] primeFactors = new int[9];
int j = 0;
// 2s that divide n
if (n % 2 == 0)
{
primeFactors[j++] = 2;
while (n % 2 == 0)
n >>= 1;
}
// N must be odd at this point
// Skip one element
for (int i = 3;
i * i <= n; i += 2)
{
if (n % i == 0)
{
// Update the prime factor
primeFactors[j++] = i;
while (n % i == 0)
n /= i;
}
}
// If n is a prime number
// greater than 2
if (n > 2)
primeFactors[j++] = n;
int []temp = new int[j];
Array.Copy(primeFactors, temp, j);
return temp;
}
// Function that finds the shortest
// subsequence
private static void findShortestSubsequence(int[] dp, int[] a,
int index,
int[] primeFactors)
{
int n = a.Length;
for (int j = index; j < n; j++)
{
int bitmask = 0;
for (int p = 0;
p < primeFactors.Length; p++)
{
// Check if the prime factor
// of first number, is also
// the prime factor of the
// rest numbers in array
if (a[j] % primeFactors[p] == 0)
{
// Set corresponding bit
// of prime factor to 1,
// it means both these
// numbers have the
// same prime factor
bitmask ^= (1 << p);
}
}
for (int i = 0;
i < dp.Length; i++)
{
// If no states encountered
// so far continue for this
// combination of bits
if (dp[i] == n + 1)
continue;
// Update this state with
// minimum ways to reach
// this state
dp[bitmask & i] = Math.Min(dp[bitmask & i],
dp[i] + 1);
}
}
}
// Function that print the minimum
// length of subsequence
private static void printMinimumLength(int[] a)
{
int min = a.Length + 1;
for (int i = 0;
i < a.Length - 1; i++)
{
// Find the prime factors of
// the first number
int[] primeFactors = findPrimeFactors(a[i]);
int n = primeFactors.Length;
int[] dp = new int[1 << n];
// Initialize the array with
// maximum steps, size of the
// array + 1 for instance
for(i = 0; i < dp.Length; i++)
dp[i] = a.Length + 1;
// Express the prime factors
// in bit representation
// Total number of set bits is
// equal to the total number
// of prime factors
int setBits = (1 << n) - 1;
// Indicates there is one
// way to reach the number
// under consideration
dp[setBits] = 1;
findShortestSubsequence(dp, a, i + 1,
primeFactors);
// State 0 corresponds
// to gcd of 1
min = Math.Min(dp[0], min);
}
// If not found such subsequence
// then print "-1"
if (min == a.Length + 1)
Console.WriteLine(-1);
// Else print the length
else
Console.WriteLine(min);
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int[] arr = {2, 6, 12, 3};
// Function Call
printMinimumLength(arr);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
// Function that finds the prime
// factors of a number
function findPrimeFactors(n)
{
// To store the prime factor
let primeFactors = new Array(9).fill(0);
let j = 0;
// 2s that divide n
if (n % 2 == 0) {
primeFactors[j++] = 2;
while (n % 2 == 0)
n >>= 1;
}
// N must be odd at this point
// Skip one element
for (let i = 3;
i * i <= n; i += 2) {
if (n % i == 0) {
// Update the prime factor
primeFactors[j++] = i;
while (n % i == 0)
n /= i;
}
}
// If n is a prime number
// greater than 2
if (n > 2)
primeFactors[j++] = n;
let PrimeFactors = new Array(j);
for(let i = 0; i < j; i++)
{
PrimeFactors[i] = primeFactors[i];
}
return PrimeFactors;
}
// Function that finds the shortest
// subsequence
function findShortestSubsequence(dp, a, index, primeFactors)
{
let n = a.length;
for (let j = index; j < n; j++) {
let bitmask = 0;
for (let p = 0;
p < primeFactors.length; p++) {
// Check if the prime factor
// of first number, is also
// the prime factor of the
// rest numbers in array
if ((a[j] % primeFactors[p]) == 0) {
// Set corresponding bit
// of prime factor to 1,
// it means both these
// numbers have the
// same prime factor
bitmask ^= (1 << p);
}
}
for (let i = 0; i < dp.length; i++) {
// If no states encountered
// so far continue for this
// combination of bits
if (dp[i] == n + 1)
continue;
// Update this state with
// minimum ways to reach
// this state
dp[bitmask & i]
= Math.min(dp[bitmask & i], dp[i] + 1);
}
}
}
// Function that print the minimum
// length of subsequence
function prletMinimumLength(a)
{
let Min = a.length + 1;
for (let i = 0; i < a.length - 1; i++) {
// Find the prime factors of
// the first number
let primeFactors = findPrimeFactors(a[i]);
let n = primeFactors.length;
// Initialize the array with
// maximum steps, size of the
// array + 1 for instance
let dp = new Array(1 << n);
for(let i = 0; i < dp.length; i++){
dp[i] = a.length + 1
}
// Express the prime factors
// in bit representation
// Total number of set bits is
// equal to the total number
// of prime factors
let setBits = (1 << n) - 1;
// Indicates there is one
// way to reach the number
// under consideration
dp[setBits] = 1;
findShortestSubsequence(dp, a, i + 1,
primeFactors);
// State 0 corresponds
// to gcd of 1
Min = Math.min(dp[0], Min);
}
// If not found such subsequence
// then print "-1"
if (Min == (a.length + 1))
document.write(-1 + "<br>");
// Else print the length
else
document.write(Min + "<br>");
}
// Driver code
// Given array arr[]
let arr = [ 2, 6, 12, 3 ];
// Function Call
prletMinimumLength(arr);
// This code is contributed by _saurabh_jaiswal
</script>
Producción
2
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)