# Count subsets having product divisible by K

Given an array **arr[]** of size **N** and an integer **K**, the task is to count the number of subsets from the given array with product of elements divisible by **K**

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr[] = {1, 2, 3, 4, 5}, K = 60Output:4Explanation:Subsets whose product of elements is divisible by K(= 60) are { {1, 2, 3, 4, 5}, {2, 3, 4, 5}, {3, 4, 5}, {1, 3, 4, 5} }

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

**Naive Approach:** The simplest approach to solve this problem is to generate all possible subsets and for each subset, check if the product of its elements is divisible by **K** or not. If found to be true, then increment the **count**. Finally, print the **count**.

**Time Complexity:** O(N * 2^{N})**Auxiliary Space:** O(N)

**Efficient Approach:** To optimize the above approach the idea is to use Dynamic programming. Below is the recurrence relation and the base case:

Recurrence Relation:

cntSubDivK(N, rem) = cntSubDivK(N – 1, (rem * arr[N – 1]) % K) + cntSubDivK(N – 1, rem).

cntSubDivK(N, rem) store the count of subset having product divisible by K.

rem: Store the remainder when K divides the product of all elements of the subset.

Base Case:

ifN == 0 and rem == 0then return1.

IfN == 0 and rem != 0then return0.

Follow the steps below to solve the problem:

- Initialize a 2D array, say
**dp[N][rem]**to compute and store the values of all subproblems of the above recurrence relation. - Finally, return the value of
**dp[N][rem]**.

Below is the implementation of the above approach:

## C++

`// 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

`// 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

`# 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#

`// 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` |

## Javascript

`<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>` |

**Output:**

16

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