Dada una array arr[] que consta de N enteros y un entero positivo X , la tarea es contar subsecuencias con GCD exactamente X .
Ejemplos:
Entrada: arr[] = {6, 4, 30} X = 2
Salida: 3
Explicación: Las subsecuencias con GCD(=2) son { {6, 4, 30}, {4, 30}, {6, 4} } . Por lo tanto, 3 es la respuesta.Entrada: arr[] = {6, 6, 6} X= 3
Salida: 0
Enfoque: El problema dado se puede resolver con la ayuda de la Programación Dinámica . Siga los pasos a continuación para resolver el problema dado.
- Defina una tabla dp 2-D dp[i][j] que indicará el número de subsecuencias válidas hasta el índice i con GCD(= j ).
- Para cada iteración tenemos 2 opciones:
- Tome el elemento actual: la tabla dp se puede actualizar como dp[i + 1][gcd(j, arr[i])] += dp[i][j] .
- Omitir el elemento actual: la tabla dp se puede actualizar como dp[i+1][j] += dp[i][j] .
- El caso base es dp[0][0] = 1 .
- Dado que el mcd de dos números nunca puede ser mayor que los dos números, los valores de j serán hasta el elemento máximo en la array . Por lo tanto, se puede resolver iterativamente y la respuesta final será dp[N][X] .
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 to find the total subsequences
// having GCD = X
int totalValidSubsequences(
vector<int> arr, int X, int N)
{
// Find the maximum element of
// the array
int mx = *max_element(
arr.begin(), arr.end());
// Check if X is greater than mx
if (X > mx) {
return 0;
}
// Make a 2-d dp table of
// size [n+1, mx + 1]
vector<vector<int> > dp(
N + 1, vector<int>(mx + 1, 0));
// Base Case
dp[0][0] = 1;
for (int i = 0; i < N; i++) {
// Iterate through all possible
// indexes
for (int j = 0; j <= mx; j++) {
// Iterate through all
// possible values
// Case 1. Skip the element
dp[i + 1][j] += dp[i][j];
// Case 2. Skip the current element
dp[i + 1][__gcd(j, arr[i])] += dp[i][j];
}
}
// Return the answer dp[N][X]
return dp[N][X];
}
// Driver Code
int main()
{
vector<int> arr = { 6, 4, 30 };
int X = 2;
int N = arr.size();
cout << totalValidSubsequences(arr, X, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.Arrays;
import java.util.Collections;
class GFG {
// Function to find maximum in arr[]
static int max(int[] arr)
{
// Initialize maximum element
int max = arr[0];
// Traverse array elements from second and
// compare every element with current max
for (int i = 1; i < arr.length; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
// Recursive function to return gcd of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to find the total subsequences
// having GCD = X
static int totalValidSubsequences(int[] arr,
int X, int N)
{
// Find the maximum element of
// the array
int mx = max(arr);
// Check if X is greater than mx
if (X > mx) {
return 0;
}
// Make a 2-d dp table of
// size [n+1, mx + 1]
int dp[][] = new int[N + 1][mx + 1];
// Base Case
dp[0][0] = 1;
for (int i = 0; i < N; i++) {
// Iterate through all possible
// indexes
for (int j = 0; j <= mx; j++) {
// Iterate through all
// possible values
// Case 1. Skip the element
dp[i + 1][j] += dp[i][j];
// Case 2. Skip the current element
dp[i + 1][gcd(j, arr[i])] += dp[i][j];
}
}
// Return the answer dp[N][X]
return dp[N][X];
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 6, 4, 30 };
int X = 2;
int N = arr.length;
System.out.println(totalValidSubsequences(arr, X, N));
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python 3 program for the above approach from math import gcd # Function to find the total subsequences # having GCD = X def totalValidSubsequences(arr, X, N): # Find the maximum element of # the array mx = max(arr) # Check if X is greater than mx if (X > mx): return 0 # Make a 2-d dp table of # size [n+1, mx + 1] dp = [[0 for i in range(mx+1)] for j in range(N + 1)] # Base Case dp[0][0] = 1 for i in range(N): # Iterate through all possible # indexes for j in range(mx+1): # Iterate through all # possible values # Case 1. Skip the element dp[i + 1][j] += dp[i][j] # Case 2. Skip the current element dp[i + 1][gcd(j, arr[i])] += dp[i][j] # Return the answer dp[N][X] return dp[N][X] # Driver Code if __name__ == '__main__': arr = [6, 4, 30] X = 2 N = len(arr) print(totalValidSubsequences(arr, X, N)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find maximum in arr[]
static int max(int []arr)
{
// Initialize maximum element
int max = arr[0];
// Traverse array elements from second and
// compare every element with current max
for (int i = 1; i < arr.Length; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
// Recursive function to return gcd of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to find the total subsequences
// having GCD = X
static int totalValidSubsequences(int[] arr,
int X, int N)
{
// Find the maximum element of
// the array
int mx = max(arr);
// Check if X is greater than mx
if (X > mx) {
return 0;
}
// Make a 2-d dp table of
// size [n+1, mx + 1]
int[,] dp = new int[N + 1, mx + 1];
// Base Case
dp[0, 0] = 1;
for (int i = 0; i < N; i++) {
// Iterate through all possible
// indexes
for (int j = 0; j <= mx; j++) {
// Iterate through all
// possible values
// Case 1. Skip the element
dp[i + 1, j] += dp[i, j];
// Case 2. Skip the current element
dp[i + 1, gcd(j, arr[i])] += dp[i, j];
}
}
// Return the answer dp[N][X]
return dp[N, X];
}
// Driver Code
public static void Main()
{
int[] arr = { 6, 4, 30 };
int X = 2;
int N = arr.Length;
Console.Write(totalValidSubsequences(arr, X, N));
}
}
// This code is contributed by _saurabh_jaiswal
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Recursive function to return gcd of a and b
function __gcd(a, b) {
if (b == 0)
return a;
return __gcd(b, a % b);
}
// Function to find the total subsequences
// having GCD = X
function totalValidSubsequences(
arr, X, N)
{
// Find the maximum element of
// the array
let mx = arr[0];
for (let i = 1; i < arr.length; i++) {
mx = Math.max(mx, arr[i]);
}
// Check if X is greater than mx
if (X > mx) {
return 0;
}
// Make a 2-d dp table of
// size [n+1, mx + 1]
let dp = new Array(N + 1);
for (let i = 0; i < N + 1; i++) {
dp[i] = new Array(mx + 1).fill(0)
}
// Base Case
dp[0][0] = 1;
for (let i = 0; i < N; i++) {
// Iterate through all possible
// indexes
for (let j = 0; j <= mx; j++) {
// Iterate through all
// possible values
// Case 1. Skip the element
dp[i + 1][j] += dp[i][j];
// Case 2. Skip the current element
dp[i + 1][__gcd(j, arr[i])] += dp[i][j];
}
}
// Return the answer dp[N][X]
return dp[N][X];
}
// Driver Code
let arr = [6, 4, 30];
let X = 2;
let N = arr.length;
document.write(totalValidSubsequences(arr, X, N));
// This code is contributed by Potta Lokesh
</script>
Producción:
3
Complejidad temporal: O(N*M), donde M es el elemento máximo del arreglo .
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA