Dada una array de N números, la tarea es contar el número de subsecuencias que tienen gcd igual a 1.
Ejemplos:
Input: a[] = {3, 4, 8, 16}
Output: 7
The subsequences are:
{3, 4}, {3, 8}, {3, 16}, {3, 4, 8},
{3, 4, 16}, {3, 8, 16}, {3, 4, 8, 16}
Input: a[] = {1, 2, 4}
Output: 4
Una solución simple es generar todas las subsecuencias o subconjuntos . Para cada subsecuencia, verifica si su GCD es 1 o no. Si es 1, incrementa el resultado.
Cuando tenemos valores en la array (por ejemplo, todos menores de 1000), podemos optimizar la solución anterior, ya que sabemos que la cantidad de GCD posibles sería pequeña. Modificamos el algoritmo recursivo de generación de subconjuntos considerando dos casos para cada elemento, lo incluimos o lo excluimos. Realizamos un seguimiento del GCD actual y, si ya contamos para este GCD, devolvemos el recuento. Entonces, cuando estamos considerando un subconjunto, algunos GCD aparecerán una y otra vez. Por lo tanto, el problema se puede resolver utilizando Programación Dinámica. A continuación se detallan los pasos para resolver el problema anterior:
- Comience desde cada índice y llame a la función recursiva tomando el elemento de índice.
- En la función recursiva, iteramos hasta llegar a N.
- Las dos llamadas recursivas se basarán en si tomamos el elemento de índice o no.
- El caso base será devolver 1 si hemos llegado al final y el mcd hasta ahora es 1.
- Dos llamadas recursivas serán func(ind+1, gcd(a[i], prevgcd)) y func(ind+1, prevgcd)
- Los subproblemas superpuestos se pueden evitar utilizando la técnica de memorización .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the number
// of subsequences with gcd 1
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Recursive function to calculate the number
// of subsequences with gcd 1 starting with
// particular index
int func(int ind, int g, int dp[][MAX], int n, int a[])
{
// Base case
if (ind == n) {
if (g == 1)
return 1;
else
return 0;
}
// If already visited
if (dp[ind][g] != -1)
return dp[ind][g];
// Either we take or we do not
int ans = func(ind + 1, g, dp, n, a)
+ func(ind + 1, gcd(a[ind], g), dp, n, a);
// Return the answer
return dp[ind][g] = ans;
}
// Function to return the number of subsequences
int countSubsequences(int a[], int n)
{
// Hash table to memoize
int dp[n][MAX];
memset(dp, -1, sizeof dp);
// Count the number of subsequences
int count = 0;
// Count for every subsequence
for (int i = 0; i < n; i++)
count += func(i + 1, a[i], dp, n, a);
return count;
}
// Driver Code
int main()
{
int a[] = { 3, 4, 8, 16 };
int n = sizeof(a) / sizeof(a[0]);
cout << countSubsequences(a, n);
return 0;
}
Java
// Java program to find the number
// of subsequences with gcd 1
class GFG
{
static final int MAX = 1000;
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Recursive function to calculate the number
// of subsequences with gcd 1 starting with
// particular index
static int func(int ind, int g, int dp[][],
int n, int a[])
{
// Base case
if (ind == n)
{
if (g == 1)
return 1;
else
return 0;
}
// If already visited
if (dp[ind][g] != -1)
return dp[ind][g];
// Either we take or we do not
int ans = func(ind + 1, g, dp, n, a)
+ func(ind + 1, gcd(a[ind], g), dp, n, a);
// Return the answer
return dp[ind][g] = ans;
}
// Function to return the
// number of subsequences
static int countSubsequences(int a[], int n)
{
// Hash table to memoize
int dp[][] = new int[n][MAX];
for(int i = 0; i < n; i++)
for(int j = 0; j < MAX; j++)
dp[i][j] = -1;
// Count the number of subsequences
int count = 0;
// Count for every subsequence
for (int i = 0; i < n; i++)
count += func(i + 1, a[i], dp, n, a);
return count;
}
// Driver Code
public static void main(String args[])
{
int a[] = { 3, 4, 8, 16 };
int n = a.length;
System.out.println(countSubsequences(a, n));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to find the number # of subsequences with gcd 1 MAX = 1000 def gcd(a, b): if (a == 0): return b return gcd(b % a, a) # Recursive function to calculate the # number of subsequences with gcd 1 # starting with particular index def func(ind, g, dp, n, a): # Base case if (ind == n): if (g == 1): return 1 else: return 0 # If already visited if (dp[ind][g] != -1): return dp[ind][g] # Either we take or we do not ans = (func(ind + 1, g, dp, n, a) + func(ind + 1, gcd(a[ind], g), dp, n, a)) # Return the answer dp[ind][g] = ans return dp[ind][g] # Function to return the number # of subsequences def countSubsequences(a, n): # Hash table to memoize dp = [[-1 for i in range(MAX)] for i in range(n)] # Count the number of subsequences count = 0 # Count for every subsequence for i in range(n): count += func(i + 1, a[i], dp, n, a) return count # Driver Code a = [3, 4, 8, 16 ] n = len(a) print(countSubsequences(a, n)) # This code is contributed by mohit kumar 29
C#
// C# program to find the number
// of subsequences with gcd 1
using System;
class GFG
{
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Recursive function to calculate the number
// of subsequences with gcd 1 starting with
// particular index
static int func(int ind, int g, int [][] dp,
int n, int [] a)
{
// Base case
if (ind == n)
{
if (g == 1)
return 1;
else
return 0;
}
// If already visited
if (dp[ind][g] != -1)
return dp[ind][g];
// Either we take or we do not
int ans = func(ind + 1, g, dp, n, a)
+ func(ind + 1, gcd(a[ind], g), dp, n, a);
// Return the answer
return dp[ind][g] = ans;
}
// Function to return the
// number of subsequences
static int countSubsequences(int [] a, int n)
{
// Hash table to memoize
int [][] dp = new int[n][];
for(int i = 0; i < n; i++)
for(int j = 0; j < 1000; j++)
dp[i][j] = -1;
// Count the number of subsequences
int count = 0;
// Count for every subsequence
for (int i = 0; i < n; i++)
count += func(i + 1, a[i], dp, n, a);
return count;
}
// Driver Code
public static void Main()
{
int [] a = { 3, 4, 8, 16 };
int n = 4;
int x = countSubsequences(a, n);
Console.Write(x);
}
}
// This code is contributed by
// mohit kumar 29
PHP
<?php
// PHP program to find the number
// of subsequences with gcd 1
$GLOBALS['MAX'] = 1000;
function gcd($a, $b)
{
if ($a == 0)
return $b;
return gcd($b % $a, $a);
}
// Recursive function to calculate the
// number of subsequences with gcd 1
// starting with particular index
function func($ind, $g, $dp, $n, $a)
{
// Base case
if ($ind == $n)
{
if ($g == 1)
return 1;
else
return 0;
}
// If already visited
if ($dp[$ind][$g] != -1)
return $dp[$ind][$g];
// Either we take or we do not
$ans = func($ind + 1, $g, $dp, $n, $a) +
func($ind + 1, gcd($a[$ind], $g),
$dp, $n, $a);
// Return the answer
$dp[$ind][$g] = $ans;
return $dp[$ind][$g] ;
}
// Function to return the number
// of subsequences
function countSubsequences($a, $n)
{
// Hash table to memoize
$dp = array(array()) ;
for($i = 0 ; $i < $n ; $i++)
for($j = 0;
$j < $GLOBALS['MAX']; $j++)
$dp[$i][$j] = -1 ;
// Count the number of subsequences
$count = 0;
// Count for every subsequence
for ($i = 0; $i < $n; $i++)
$count += func($i + 1, $a[$i],
$dp, $n, $a);
return $count;
}
// Driver Code
$a = array(3, 4, 8, 16);
$n = sizeof($a) ;
echo countSubsequences($a, $n);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript program to find the number
// of subsequences with gcd 1
var MAX = 1000;
function gcd(a , b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
// Recursive function to calculate the number
// of subsequences with gcd 1 starting with
// particular index
function func(ind , g , dp , n , a) {
// Base case
if (ind == n) {
if (g == 1)
return 1;
else
return 0;
}
// If already visited
if (dp[ind][g] != -1)
return dp[ind][g];
// Either we take or we do not
var ans = func(ind + 1, g, dp, n, a) +
func(ind + 1, gcd(a[ind], g), dp, n, a);
// Return the answer
return dp[ind][g] = ans;
}
// Function to return the
// number of subsequences
function countSubsequences(a , n) {
// Hash table to memoize
var dp = Array(n).fill().map(()=>Array(MAX).fill(0));
for (i = 0; i < n; i++)
for (j = 0; j < MAX; j++)
dp[i][j] = -1;
// Count the number of subsequences
var count = 0;
// Count for every subsequence
for (i = 0; i < n; i++)
count += func(i + 1, a[i], dp, n, a);
return count;
}
// Driver Code
var a = [ 3, 4, 8, 16 ];
var n = a.length;
document.write(countSubsequences(a, n));
// This code contributed by Rajput-Ji
</script>
Producción
7
Complejidad de tiempo: O(logN*N 2 ), ya que estamos llamando recursivamente a la función dos veces pero estamos usando la memorización y la función GCD costará O(logN). Donde N es el número de elementos de la array.
Espacio auxiliar: O(N*1000), ya que estamos usando espacio extra para la array DP. Donde N es el número de elementos de la array.
Solución alternativa: Cuente el número de subconjuntos de un conjunto con GCD igual a un número dado
Enfoque de programación dinámica para este problema sin memorización:
Básicamente, el enfoque será hacer una array 2d en la que la coordenada i será la posición de los elementos de la array dada y la coordenada j serán números del 0 al 100, es decir. gcd puede variar de 0 a 100 si los elementos de la array no son lo suficientemente grandes. iteraremos en la array dada y la array 2d almacenará información que hasta la enésima posición en la que cuántas subsecuencias tienen gcd varían de 1 a 100. Más adelante, agregaremos dp[i][1] para obtener todas las subsecuencias que tienen mcd como 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// This function calculates
// gcd of two number
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// This function will return total
// subsequences
int countSubsequences(int arr[], int n)
{
// Declare a dp 2d array
long long int dp[n][101] = {0};
// Iterate i from 0 to n - 1
for(int i = 0; i < n; i++)
{
dp[i][arr[i]] = 1;
// Iterate j from i - 1 to 0
for(int j = i - 1; j >= 0; j--)
{
if(arr[j] < arr[i])
{
// Iterate k from 0 to 100
for(int k = 0; k <= 100; k++)
{
// Find gcd of two number
int GCD = gcd(arr[i], k);
// dp[i][GCD] is summation of
// dp[i][GCD] and dp[j][k]
dp[i][GCD] = dp[i][GCD] +
dp[j][k];
}
}
}
}
// Add all elements of dp[i][1]
long long int sum = 0;
for(int i = 0; i < n; i++)
{
sum=(sum + dp[i][1]);
}
// Return sum
return sum;
}
// Driver code
int main()
{
int a[] = { 3, 4, 8, 16 };
int n = sizeof(a) / sizeof(a[0]);
// Function Call
cout << countSubsequences(a, n);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// This function calculates
// gcd of two number
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// This function will return total
// subsequences
static long countSubsequences(int arr[],
int n)
{
// Declare a dp 2d array
long dp[][] = new long[n][101];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 101; j++)
{
dp[i][j] = 0;
}
}
// Iterate i from 0 to n - 1
for(int i = 0; i < n; i++)
{
dp[i][arr[i]] = 1;
// Iterate j from i - 1 to 0
for(int j = i - 1; j >= 0; j--)
{
if (arr[j] < arr[i])
{
// Iterate k from 0 to 100
for(int k = 0; k <= 100; k++)
{
// Find gcd of two number
int GCD = gcd(arr[i], k);
// dp[i][GCD] is summation of
// dp[i][GCD] and dp[j][k]
dp[i][GCD] = dp[i][GCD] +
dp[j][k];
}
}
}
}
// Add all elements of dp[i][1]
long sum = 0;
for(int i = 0; i < n; i++)
{
sum = (sum + dp[i][1]);
}
// Return sum
return sum;
}
// Driver code
public static void main(String args[])
{
int a[] = { 3, 4, 8, 16 };
int n = a.length;
// Function Call
System.out.println(countSubsequences(a, n));
}
}
// This code is contributed by bolliranadheer
Python3
# Python3 program for the # above approach # This function calculates # gcd of two number def gcd(a, b): if (b == 0): return a; return gcd(b, a % b); # This function will return total # subsequences def countSubsequences(arr, n): # Declare a dp 2d array dp = [[0 for i in range(101)] for j in range(n)] # Iterate i from 0 to n - 1 for i in range(n): dp[i][arr[i]] = 1; # Iterate j from i - 1 to 0 for j in range(i - 1, -1, -1): if (arr[j] < arr[i]): # Iterate k from 0 to 100 for k in range(101): # Find gcd of two number GCD = gcd(arr[i], k); # dp[i][GCD] is summation of # dp[i][GCD] and dp[j][k] dp[i][GCD] = dp[i][GCD] + dp[j][k]; # Add all elements of dp[i][1] sum = 0; for i in range(n): sum = (sum + dp[i][1]); # Return sum return sum; # Driver code if __name__=='__main__': a = [ 3, 4, 8, 16 ] n = len(a) # Function Call print(countSubsequences(a,n)) # This code is contributed by Pratham76
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// This function calculates
// gcd of two number
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// This function will return total
// subsequences
static long countSubsequences(int []arr,
int n)
{
// Declare a dp 2d array
long [,]dp = new long[n, 101];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 101; j++)
{
dp[i, j] = 0;
}
}
// Iterate i from 0 to n - 1
for(int i = 0; i < n; i++)
{
dp[i, arr[i]] = 1;
// Iterate j from i - 1 to 0
for(int j = i - 1; j >= 0; j--)
{
if (arr[j] < arr[i])
{
// Iterate k from 0 to 100
for(int k = 0; k <= 100; k++)
{
// Find gcd of two number
int GCD = gcd(arr[i], k);
// dp[i,GCD] is summation of
// dp[i,GCD] and dp[j,k]
dp[i, GCD] = dp[i, GCD] +
dp[j, k];
}
}
}
}
// Add all elements of dp[i,1]
long sum = 0;
for(int i = 0; i < n; i++)
{
sum = (sum + dp[i, 1]);
}
// Return sum
return sum;
}
// Driver code
public static void Main(string []args)
{
int []a = { 3, 4, 8, 16 };
int n = a.Length;
// Function Call
Console.WriteLine(countSubsequences(a, n));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// javascript program for the
// above approach
// This function calculates
// gcd of two number
function gcd(a , b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
// This function will return total
// subsequences
function countSubsequences(arr , n) {
// Declare a dp 2d array
var dp = Array(n).fill().map(()=>Array(101).fill(0));
for (i = 0; i < n; i++) {
for (j = 0; j < 101; j++) {
dp[i][j] = 0;
}
}
// Iterate i from 0 to n - 1
for (i = 0; i < n; i++) {
dp[i][arr[i]] = 1;
// Iterate j from i - 1 to 0
for (j = i - 1; j >= 0; j--) {
if (arr[j] < arr[i]) {
// Iterate k from 0 to 100
for (k = 0; k <= 100; k++) {
// Find gcd of two number
var GCD = gcd(arr[i], k);
// dp[i][GCD] is summation of
// dp[i][GCD] and dp[j][k]
dp[i][GCD] = dp[i][GCD] + dp[j][k];
}
}
}
}
// Add all elements of dp[i][1]
var sum = 0;
for (i = 0; i < n; i++) {
sum = (sum + dp[i][1]);
}
// Return sum
return sum;
}
// Driver code
var a = [ 3, 4, 8, 16 ];
var n = a.length;
// Function Call
document.write(countSubsequences(a, n));
// This code contributed by aashish1995
</script>
Producción
7
Complejidad de tiempo: O(100*logN*N 2 ), ya que estamos usando bucles anidados y la función GCD costará O(logN). Donde N es el número de elementos de la array.
Espacio auxiliar: O(N*100), ya que estamos usando espacio extra para la array DP. Donde N es el número de elementos de la array.