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 4Input: 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 Kint 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 Kint 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 Codeint 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 approachimport java.util.*; class GFG{ static int M = 1000; // Function to find the count of subsets// whose product of elements is equal to Kstatic 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 Kstatic 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 codepublic 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 approachM = 1000# Function to find the count of subsets# whose product of elements is equal to Kdef 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 Kdef 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 Codeif __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 Kstatic 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 Kstatic 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 codepublic 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 approachlet M = 1000; // Function to find the count of subsets// whose product of elements is equal to Kfunction 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 Kfunction 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:
8
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 Kint 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 Codeint 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 Kdef 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 Codearr = [1, 1, 2, 2, 3, 4]K = 4N = 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:
8
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
