Cuente los subconjuntos que tienen un producto divisible por K

Dada una array arr[] de tamaño N y un número entero K , la tarea es contar el número de subconjuntos de la array dada con el producto de elementos divisibles por K

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4, 5}, K = 60
Salida: 4
Explicación: Los subconjuntos cuyo producto de elementos es divisible por K(= 60) son { {1, 2, 3, 4, 5}, {2, 3, 4, 5}, {3, 4, 5}, {1, 3, 4, 5} }

Entrada: arr[] = {1, 2, 3, 4, 5, 6}, K = 60
Salida: 16

Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los subconjuntos posibles y, para cada subconjunto, verificar si el producto de sus elementos es divisible por K o no. Si se encuentra que es cierto, entonces incremente el conteo . Finalmente, imprima el conteo .

Complejidad de Tiempo: O(N * 2 ^N )
Espacio Auxiliar: O(N)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la programación dinámica . A continuación se muestra la relación de recurrencia y el caso base:

Relación de recurrencia: 
cntSubDivK(N, rem) = cntSubDivK(N – 1, (rem * arr[N – 1]) % K) + cntSubDivK(N – 1, rem). 
cntSubDivK(N, rem) almacena el recuento del subconjunto que tiene un producto divisible por K. 
rem: almacena el resto cuando K divide el producto de todos los elementos del subconjunto. 
 

Caso base: 
si N == 0 y rem == 0 , devuelve 1 . 
Si N == 0 y rem != 0 entonces devuelve 0 .

Siga los pasos a continuación para resolver el problema:

• Inicialice una array 2D , digamos dp[N][rem] para calcular y almacenar los valores de todos los subproblemas de la relación de recurrencia anterior.
• Finalmente, devuelve el valor de dp[N][rem] .

A continuación se muestra la implementación del enfoque anterior:

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the subsets whose
// product of elements is divisible by K
int cntSubDivK(int arr[], int N, int K,
               int rem, vector<vector<int> >& dp)
{
    // If count of elements
    // in the array is 0
    if (N == 0) {
 
        // If rem is 0, then return 1
        // Otherwise, return 0
        return rem == 0;
    }
 
    // If already computed
    // subproblem occurred
    if (dp[N][rem] != -1) {
        return dp[N][rem];
    }
 
    // Stores count of subsets having product
    // divisible by K when arr[N - 1]
    // present in the subset
    int X = cntSubDivK(arr, N - 1, K,
                       (rem * arr[N - 1]) % K, dp);
 
    // Stores count of subsets having product
    // divisible by K when arr[N - 1] not
    // present in the subset
    int Y = cntSubDivK(arr, N - 1, K,
                       rem, dp);
 
    // Return total subset
    return X + Y;
}
 
// Utility Function to count the subsets whose
// product of elements is divisible by K
int UtilCntSubDivK(int arr[], int N, int K)
{
 
    // Initialize a 2D array to store values
    // of overlapping subproblems
    vector<vector<int> > dp(N + 1,
                            vector<int>(K + 1, -1));
 
    return cntSubDivK(arr, N, K, 1, dp);
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int K = 60;
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << UtilCntSubDivK(arr, N, K);
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
   
// Function to count the subsets whose
// product of elements is divisible by K
static int cntSubDivK(int arr[], int N, int K,
                      int rem, int[][]dp)
{
     
    // If count of elements
    // in the array is 0
    if (N == 0)
    {
         
        // If rem is 0, then return 1
        // Otherwise, return 0
        return rem == 0 ? 1 : 0;
    }
 
    // If already computed
    // subproblem occurred
    if (dp[N][rem] != -1)
    {
        return dp[N][rem];
    }
 
    // Stores count of subsets having product
    // divisible by K when arr[N - 1]
    // present in the subset
    int X = cntSubDivK(arr, N - 1, K,
                       (rem * arr[N - 1]) % K, dp);
 
    // Stores count of subsets having product
    // divisible by K when arr[N - 1] not
    // present in the subset
    int Y = cntSubDivK(arr, N - 1, K,
                       rem, dp);
 
    // Return total subset
    return X + Y;
}
 
// Utility Function to count the subsets whose
// product of elements is divisible by K
static int UtilCntSubDivK(int arr[], int N, int K)
{
     
    // Initialize a 2D array to store values
    // of overlapping subproblems
    int [][]dp = new int[N + 1][K + 1];
     
    for(int i = 0; i < N + 1; i++)
    {
        for(int j = 0; j < K + 1; j++)
            dp[i][j] = -1;
    }
    return cntSubDivK(arr, N, K, 1, dp);
}
 
// Driver Code
public static void main(String args[])
{
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int K = 60;
    int N = arr.length;
     
    System.out.println(UtilCntSubDivK(arr, N, K));
}
}
 
// This code is contributed by SURENDRA_GANGWAR

# Python3 program to
# implement the above
# approach
 
# Function to count the
# subsets whose product
# of elements is divisible
# by K
def cntSubDivK(arr, N, K,
               rem, dp):
 
    # If count of elements
    # in the array is 0
    if (N == 0):
 
        # If rem is 0, then
        # return 1 Otherwise,
        # return 0
        return rem == 0
 
    # If already computed
    # subproblem occurred
    if (dp[N][rem] != -1):
        return dp[N][rem]
 
    # Stores count of subsets
    # having product divisible
    # by K when arr[N - 1]
    # present in the subset
    X = cntSubDivK(arr, N - 1, K,
                   (rem * arr[N - 1]) % K, dp)
 
    # Stores count of subsets having
    # product divisible by K when
    # arr[N - 1] not present in
    # the subset
    Y = cntSubDivK(arr, N - 1,
                   K, rem, dp)
 
    # Return total subset
    return X + Y
 
# Utility Function to count
# the subsets whose product of
# elements is divisible by K
def UtilCntSubDivK(arr, N, K):
 
    # Initialize a 2D array to
    # store values of overlapping
    # subproblems
    dp = [[-1 for x in range(K + 1)]
              for y in range(N + 1)]
 
    return cntSubDivK(arr, N,
                      K, 1, dp)
   
# Driver Code
if __name__ == "__main__":
 
    arr = [1, 2, 3,
           4, 5, 6]
    K = 60
    N = len(arr)
    print(UtilCntSubDivK(arr, N, K))
 
# This code is contributed by Chitranayal

// C# program to implement
// the above approach
using System;
 
class GFG{
     
// Function to count the subsets whose
// product of elements is divisible by K
static int cntSubDivK(int[] arr, int N, int K,
                      int rem, int[,] dp)
{
     
    // If count of elements
    // in the array is 0
    if (N == 0)
    {
         
        // If rem is 0, then return 1
        // Otherwise, return 0
        return rem == 0 ? 1 : 0;
    }
  
    // If already computed
    // subproblem occurred
    if (dp[N, rem] != -1)
    {
        return dp[N, rem];
    }
     
    // Stores count of subsets having product
    // divisible by K when arr[N - 1]
    // present in the subset
    int X = cntSubDivK(arr, N - 1, K,
                      (rem * arr[N - 1]) % K, dp);
                       
    // Stores count of subsets having product
    // divisible by K when arr[N - 1] not
    // present in the subset
    int Y = cntSubDivK(arr, N - 1, K,
                       rem, dp);
                        
    // Return total subset
    return X + Y;
}
  
// Utility Function to count the subsets whose
// product of elements is divisible by K
static int UtilCntSubDivK(int[] arr, int N, int K)
{
     
    // Initialize a 2D array to store values
    // of overlapping subproblems
    int[,] dp = new int[N + 1, K + 1];
      
    for(int i = 0; i < N + 1; i++)
    {
        for(int j = 0; j < K + 1; j++)
            dp[i, j] = -1;
    }
    return cntSubDivK(arr, N, K, 1, dp);
}
 
// Driver code
static void Main()
{
    int[] arr = { 1, 2, 3, 4, 5, 6 };
    int K = 60;
    int N = arr.Length;
 
    Console.WriteLine(UtilCntSubDivK(arr, N, K));
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to count the subsets whose
// product of elements is divisible by K
function cntSubDivK(arr, N, K, rem, dp)
{
      
    // If count of elements
    // in the array is 0
    if (N == 0)
    {
          
        // If rem is 0, then return 1
        // Otherwise, return 0
        return rem == 0 ? 1 : 0;
    }
  
    // If already computed
    // subproblem occurred
    if (dp[N][rem] != -1)
    {
        return dp[N][rem];
    }
  
    // Stores count of subsets having product
    // divisible by K when arr[N - 1]
    // present in the subset
    let X = cntSubDivK(arr, N - 1, K,
                 (rem * arr[N - 1]) % K, dp);
  
    // Stores count of subsets having product
    // divisible by K when arr[N - 1] not
    // present in the subset
    let Y = cntSubDivK(arr, N - 1, K,
                       rem, dp);
  
    // Return total subset
    return X + Y;
}
  
// Utility Function to count the subsets whose
// product of elements is divisible by K
function UtilCntSubDivK(arr, N, K)
{
      
    // Initialize a 2D array to store values
    // of overlapping subproblems
    let dp = new Array(N + 1);
      
    // Loop to create 2D array using 1D array
    for(var i = 0; i < dp.length; i++)
    {
        dp[i] = new Array(2);
    }
      
    for(let i = 0; i < N + 1; i++)
    {
        for(let j = 0; j < K + 1; j++)
            dp[i][j] = -1;
    }
    return cntSubDivK(arr, N, K, 1, dp);
}
 
// Driver Code
let arr = [ 1, 2, 3, 4, 5, 6 ];
let K = 60;
let N = arr.length;
  
document.write(UtilCntSubDivK(arr, N, K));
 
// This code is contribute by target_2
 
</script>

16

Complejidad de tiempo: O(N * K)
Complejidad de espacio: O(N * K)