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 the product of elements divisible by K
Examples:
Input: arr[] = {1, 2, 3, 4, 5}, K = 60
Output: 4
Explanation: 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 = 60
Output: 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 * 2N)
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:
if N == 0 and rem == 0 then return 1.
If N == 0 and rem != 0 then return 0.
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 Kint 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); dp[N][rem] = X + Y; // Return total subset return X + Y;}// Utility Function to count the subsets whose// product of elements is divisible by Kint 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 Codeint 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 approachimport 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); dp[N][rem] = X + Y; // 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 Kdef 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) dp[N][rem] = X + Y # Return total subset return X + Y# Utility Function to count# the subsets whose product of# elements is divisible by Kdef 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 Codeif __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#
// Online C# Editor for free// Write, Edit and Run your C# code using C# Online Compiler// C# program to implement// the above approachusing 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); dp[N, rem] = X + Y; // 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 Kfunction 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); dp[N][rem] = X + Y; // Return total subset return X + Y;} // Utility Function to count the subsets whose// product of elements is divisible by Kfunction 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 Codelet arr = [ 1, 2, 3, 4, 5, 6 ];let K = 60;let N = arr.length; document.write(UtilCntSubDivK(arr, N, K));// This code is contributed by target_2</script> |
Output:
16
Time Complexity: O(N * K)
Space Complexity: 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!