Count subsets in an array having product K

0 0 10 minutes read

Given an array arr[] of size N, the task is to find the count of all subsets from the given array whose product of is equal to K.

Examples:

Input: arr[] = { 1, 1, 2, 2, 3 }, K = 4
Output: 4
Explanation:
Subsets with product equal to K(= 4) are: { { arr[0], arr[1], arr[2], arr[3] }, { arr[0], arr[2], arr[3] }, { arr[1], arr[2], arr[3] }, { arr[2], arr[3] } } .
Therefore, the required output is 4

Input: arr[] = { 1, 1, 2, 2, 3, 4 }, K = 4
Output: 8

Approach: The problem can be solved using Dynamic Programming using the following recurrence relation:

cntSub(idx, prod) = cntSub(idx – 1, prod * arr[i]) + cntSub(idx – 1, prod)

idx: Stores index of an array element
prod: Stores product of elements of a subset
cntSub(i, prod): Stores the count of subsets from the subarray { arr[i], …, arr[N – 1] } whose product is equal to prod.

Follow the steps below to solve the problem:

Initialize a 2D array, say dp[][], to store the overlapping subproblems of the above recurrence relation.
Using the above recurrence relation, calculate the count of subsets whose product of elements is equal to K.
Finally, print the value of dp[N – 1][K].

Below is the implementation of the above approach:

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
#define M 1000
 
// Function to find the count of subsets
// whose product of elements is equal to K
int cntSub(int arr[], int idx,
           int prod, int K, int dp[][M])
{
    // Base Case
    if (idx < 0) {
 
        return (prod == K);
    }
 
    // If an already computed
    // subproblem occurred
    if (dp[idx][prod] != -1) {
 
        return dp[idx][prod];
    }
 
    // Count subsets including idx-th
    // element in the subset
    int X = cntSub(arr, idx - 1,
                   prod * arr[idx], K, dp);
 
    // Count subsets without including
    // idx-th element in the subset
    int Y = cntSub(arr, idx - 1,
                   prod, K, dp);
 
    return dp[idx][prod] = X + Y;
}
 
// Utility function to count subsets in
// an array whose product is equal to K
int UtilcntSub(int arr[], int N, int K)
{
    // dp[i][j]: Stores numberof subsets
    // with product j up to the i-th element
    int dp[N][M];
 
    // Initialize dp[][] to -1
    memset(dp, -1, sizeof(dp));
 
    cout << cntSub(arr, N - 1, 1, K, dp);
}
 
// Driver Code
int main()
{
 
    int arr[] = { 1, 1, 2, 2, 3, 4 };
 
    int K = 4;
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    UtilcntSub(arr, N, K);
}

Java

// Java program to implement
// the above approach
import java.util.*;
   
class GFG{
       
static int M = 1000;
  
// Function to find the count of subsets
// whose product of elements is equal to K
static int cntSub(int arr[], int idx,
                  int prod, int K, int dp[][])
{
     
    // Base Case
    if (idx < 0) 
    {
        if (prod == K)
            return 1;
        else
            return 0;
    }
  
    // If an already computed
    // subproblem occurred
    if (dp[idx][prod] != -1)
    {
        return dp[idx][prod];
    }
  
    // Count subsets including idx-th
    // element in the subset
    int X = cntSub(arr, idx - 1,
                   prod * arr[idx], K, dp);
  
    // Count subsets without including
    // idx-th element in the subset
    int Y = cntSub(arr, idx - 1,
                   prod, K, dp);
  
    return dp[idx][prod] = X + Y;
}
  
// Utility function to count subsets in
// an array whose product is equal to K
static void UtilcntSub(int arr[], int N, int K)
{
     
    // dp[i][j]: Stores numberof subsets
    // with product j up to the i-th element
    int[][] dp = new int[N][M];
  
    // Initialize dp[][] to -1
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            dp[i][j] = -1;
        }
    }
 
    System.out.print(cntSub(arr, N - 1, 1, K, dp));
}
   
// Driver code
public static void main(String[] args)
{
    int[] arr = { 1, 1, 2, 2, 3, 4 };
  
    int K = 4;
  
    int N = arr.length;
  
    UtilcntSub(arr, N, K);
}
}
 
// This code is contributed by code_hunt

Python3

# Python program to implement
# the above approach
M = 1000
 
# Function to find the count of subsets
# whose product of elements is equal to K
def cntSub(arr, idx, prod, K):
    global dp
     
    # Base Case
    if (idx < 0):
        return (prod == K)
 
    # If an already computed
    # subproblem occurred
    if (dp[idx][prod] != -1):
        return dp[idx][prod]
 
    # Count subsets including idx-th
    # element in the subset
    X = cntSub(arr, idx - 1, prod * arr[idx], K)
 
    # Count subsets without including
    # idx-th element in the subset
    Y = cntSub(arr, idx - 1, prod, K)
    dp[idx][prod] = X + Y
    return dp[idx][prod]
 
# Utility function to count subsets in
# an array whose product is equal to K
def UtilcntSub(arr, N, K):
   
    # dp[i][j]: Stores numberof subsets
    # with product j up to the i-th element
    print (cntSub(arr, N - 1, 1, K))
     
# Driver Code
if __name__ == '__main__':
    dp = [[-1 for i in range(1000)] for i in range(1000)]
    arr = [1, 1, 2, 2, 3, 4]
    K = 4
    N = len(arr)
    UtilcntSub(arr, N, K)
 
# This code is contributed by mohit kumar 29

C#

// C# program to implement
// the above approach  
using System;
class GFG
{
  
static int M = 1000;
   
// Function to find the count of subsets
// whose product of elements is equal to K
static int cntSub(int[] arr, int idx,
                  int prod, int K, int[,] dp)
{
      
    // Base Case
    if (idx < 0) 
    {
        if (prod == K)
            return 1;
        else
            return 0;
    }
   
    // If an already computed
    // subproblem occurred
    if (dp[idx, prod] != -1)
    {
        return dp[idx, prod];
    }
   
    // Count subsets including idx-th
    // element in the subset
    int X = cntSub(arr, idx - 1,
                   prod * arr[idx], K, dp);
   
    // Count subsets without including
    // idx-th element in the subset
    int Y = cntSub(arr, idx - 1,
                   prod, K, dp);
   
    return dp[idx, prod] = X + Y;
}
   
// Utility function to count subsets in
// an array whose product is equal to K
static void UtilcntSub(int[] arr, int N, int K)
{
      
    // dp[i][j]: Stores numberof subsets
    // with product j up to the i-th element
    int[,] dp = new int[N, M];
   
    // Initialize dp[][] to -1
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            dp[i, j] = -1;
        }
    }
  
    Console.Write(cntSub(arr, N - 1, 1, K, dp));
}
  
// Driver code
public static void Main()
{
    int[] arr = { 1, 1, 2, 2, 3, 4 };
    int K = 4;  
    int N = arr.Length;  
    UtilcntSub(arr, N, K);
}
}
 
// This code is contributed by susmitakundugoaldanga

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
let M = 1000;
   
// Function to find the count of subsets
// whose product of elements is equal to K
function cntSub(arr, idx,
                  prod, K, dp)
{
      
    // Base Case
    if (idx < 0)
    {
        if (prod == K)
            return 1;
        else
            return 0;
    }
   
    // If an already computed
    // subproblem occurred
    if (dp[idx][prod] != -1)
    {
        return dp[idx][prod];
    }
   
    // Count subsets including idx-th
    // element in the subset
    let X = cntSub(arr, idx - 1,
                   prod * arr[idx], K, dp);
   
    // Count subsets without including
    // idx-th element in the subset
    let Y = cntSub(arr, idx - 1,
                   prod, K, dp);
   
    return dp[idx][prod] = X + Y;
}
   
// Utility function to count subsets in
// an array whose product is equal to K
function UtilcntSub(arr, N, K)
{
      
    // dp[i][j]: Stores numberof subsets
    // with product j up to the i-th element
    let dp = new Array(N);
     
    // Loop to create 2D array using 1D array
    for (var i = 0; i < dp.length; i++) {
        dp[i] = new Array(2);
    }
   
    // Initialize dp[][] to -1
    for(let i = 0; i < N; i++)
    {
        for(let j = 0; j < M; j++)
        {
            dp[i][j] = -1;
        }
    }
  
    document.write(cntSub(arr, N - 1, 1, K, dp));
}
      
 
// Driver code
         
        let arr = [ 1, 1, 2, 2, 3, 4 ];
   
    let K = 4;
   
    let N = arr.length;
   
    UtilcntSub(arr, N, K);
 
</script>

Output:

Time Complexity: O(N * K)
Auxiliary Space: O(N * K)

Efficient approach : Using DP Tabulation method ( Iterative approach )

The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memorization(top-down) because memorization method needs extra stack space of recursion calls.

Steps to solve this problem :

Create a vector to store the solution of the subproblems.
Initialize the table with base cases
Fill up the table iteratively
Return the final solution

Implementation :

C++

#include <bits/stdc++.h>
using namespace std;
 
#define M 1000
 
// Utility function to count subsets in
// an array whose product is equal to K
int UtilcntSub(int arr[], int N, int K)
{
    // dp[i][j]: Stores number of subsets with product j up to the i-th element
    int dp[N][M];
 
    // Initialize dp[][] to 0
    memset(dp, 0, sizeof(dp));
 
    // Base Case: if product of 0 elements is K
    if (K == 1) {
        dp[0][1] = 1;
    }
 
    // Fill the first row of dp[][] when i = 0
    for (int j = 1; j <= K; j++) {
        if (arr[0] == j) {
            dp[0][j] = 1;
        }
    }
 
    // Fill the remaining rows of dp[][]
    for (int i = 1; i < N; i++) {
        for (int j = 1; j <= K; j++) {
            if (arr[i] == j) {
                dp[i][j] = 1;
            }
            dp[i][j] += dp[i-1][j];
            if (j % arr[i] == 0) {
                dp[i][j] += dp[i-1][j/arr[i]];
            }
        }
    }
 
    return dp[N-1][K];
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 1, 2, 2, 3, 4 };
    int K = 4;
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << UtilcntSub(arr, N, K);
}
// this code is contributed by bhardwajji

Java

import java.util.Arrays;
 
public class Main {
    static final int M = 1000;
 
    // Utility function to count subsets in
    // an array whose product is equal to K
    static int UtilcntSub(int[] arr, int N, int K)
    {
        // dp[i][j]: Stores number of subsets with product j 
       // up to the i-th element
        int[][] dp = new int[N][M];
 
        // Initialize dp[][] to 0
        for (int[] row : dp) {
            Arrays.fill(row, 0);
        }
 
        // Base Case: if product of 0 elements is K
        if (K == 1) {
            dp[0][1] = 1;
        }
 
        // Fill the first row of dp[][] when i = 0
        for (int j = 1; j <= K; j++) {
            if (arr[0] == j) {
                dp[0][j] = 1;
            }
        }
 
        // Fill the remaining rows of dp[][]
        for (int i = 1; i < N; i++) {
            for (int j = 1; j <= K; j++) {
                if (arr[i] == j) {
                    dp[i][j] = 1;
                }
                dp[i][j] += dp[i-1][j];
                if (j % arr[i] == 0) {
                    dp[i][j] += dp[i-1][j/arr[i]];
                }
            }
        }
 
        return dp[N-1][K];
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 1, 1, 2, 2, 3, 4 };
        int K = 4;
        int N = arr.length;
        System.out.println(UtilcntSub(arr, N, K));
    }
}

Python3

# Utility function to count subsets in
# an array whose product is equal to K
 
 
def UtilcntSub(arr, N, K):
    # dp[i][j]: Stores number of subsets with product j up to the i-th element
    dp = [[0 for j in range(1000)] for i in range(N)]
 
    # Base Case: if product of 0 elements is K
    if K == 1:
        dp[0][1] = 1
 
    # Fill the first row of dp[][] when i = 0
    for j in range(1, K+1):
        if arr[0] == j:
            dp[0][j] = 1
 
    # Fill the remaining rows of dp[][]
    for i in range(1, N):
        for j in range(1, K+1):
            if arr[i] == j:
                dp[i][j] = 1
            dp[i][j] += dp[i-1][j]
            if j % arr[i] == 0:
                dp[i][j] += dp[i-1][j//arr[i]]
 
    return dp[N-1][K]
 
 
# Driver Code
arr = [1, 1, 2, 2, 3, 4]
K = 4
N = len(arr)
print(UtilcntSub(arr, N, K))

C#

using System;
 
public class Program
{
 
  // Utility function to count subsets in
  // an array whose product is equal to K
  public static int UtilcntSub(int[] arr, int N, int K)
  {
 
    // dp[i][j]: Stores number of subsets
    // with product j up to the i-th element
    int[,] dp = new int[N, 1000];
 
    // Initialize dp[,] to 0
    for (int i = 0; i < N; i++)
    {
      for (int j = 0; j < 1000; j++)
      {
        dp[i, j] = 0;
      }
    }
 
    // Base Case: if product of 0 elements is K
    if (K == 1)
    {
      dp[0, 1] = 1;
    }
 
    // Fill the first row of dp[,] when i = 0
    for (int j = 1; j <= K; j++)
    {
      if (arr[0] == j)
      {
        dp[0, j] = 1;
      }
    }
 
    // Fill the remaining rows of dp[,]
    for (int i = 1; i < N; i++)
    {
      for (int j = 1; j <= K; j++)
      {
        if (arr[i] == j)
        {
          dp[i, j] = 1;
        }
        dp[i, j] += dp[i - 1, j];
        if (j % arr[i] == 0)
        {
          dp[i, j] += dp[i - 1, j / arr[i]];
        }
      }
    }
 
    return dp[N - 1, K];
  }
 
  // Driver Code
  public static void Main()
  {
    int[] arr = { 1, 1, 2, 2, 3, 4 };
    int K = 4;
    int N = arr.Length;
    Console.WriteLine(UtilcntSub(arr, N, K));
  }
}

Javascript

function UtilcntSub(arr, N, K) {
  const dp = new Array(N).fill(0).map(() => new Array(1000).fill(0));
 
  if (K === 1) {
    dp[0][1] = 1;
  }
 
  for (let j = 1; j <= K; j++) {
    if (arr[0] === j) {
      dp[0][j] = 1;
    }
  }
 
  for (let i = 1; i < N; i++) {
    for (let j = 1; j <= K; j++) {
      if (arr[i] === j) {
        dp[i][j] = 1;
      }
      dp[i][j] += dp[i - 1][j];
      if (j % arr[i] === 0) {
        dp[i][j] += dp[i - 1][j / arr[i]];
      }
    }
  }
 
  return dp[N - 1][K];
}
 
const arr = [1, 1, 2, 2, 3, 4];
const K = 4;
const N = arr.length;
console.log(UtilcntSub(arr, N, K));

Output:

Time Complexity: O(N * K)
Auxiliary Space: O(N * K)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!