Given an array arr[] of N integers and an integer M, the task is to find the number of non-empty subsequences such that the sum of the subsequence is divisible by M.
Examples:
Input: arr[] = {1, 2, 3}, M = 1
Output: 7
Number of non-empty subsets of this array are 7.
Since m = 1, m will divide all the possible subsets.
Input: arr[] = {1, 2, 3}, M = 2
Output: 3
Approach: A dynamic programming-based approach with O(N * SUM) time complexity where N is the length of the array and SUM is the sum of all the array elements has been discussed in this article.
In this article, an improvement over the previous approach will be discussed. Instead of the sum as one of the states of DP, (sum % m) will be used as one of the states of the DP as it is sufficient. Thus, the time complexity boils down to O(m * N).
Recurrence relation:
dp[i][curr] = dp[i + 1][(curr + arr[i]) % m] + dp[i + 1][curr]
Let’s define the states now, dp[i][curr] simply means number of subsets of the sub-array arr[i…N-1] such that (sum of its element + curr) % m = 0.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define maxN 20#define maxM 10// To store the states of DPint dp[maxN][maxM];bool v[maxN][maxM];// Function to find the required countint findCnt(int* arr, int i, int curr, int n, int m){ // Base case if (i == n) { if (curr == 0) return 1; else return 0; } // If the state has been solved before // return the value of the state if (v[i][curr]) return dp[i][curr]; // Setting the state as solved v[i][curr] = 1; // Recurrence relation return dp[i][curr] = findCnt(arr, i + 1, curr, n, m) + findCnt(arr, i + 1, (curr + arr[i]) % m, n, m);}// Driver codeint main(){ int arr[] = { 3, 3, 3, 3 }; int n = sizeof(arr) / sizeof(int); int m = 6; cout << findCnt(arr, 0, 0, n, m) - 1; return 0;} |
Java
// Java implementation of the approachclass GFG{static int maxN = 20;static int maxM = 10;// To store the states of DPstatic int [][]dp = new int[maxN][maxM];static boolean [][]v = new boolean[maxN][maxM];// Function to find the required countstatic int findCnt(int[] arr, int i, int curr, int n, int m){ // Base case if (i == n) { if (curr == 0) return 1; else return 0; } // If the state has been solved before // return the value of the state if (v[i][curr]) return dp[i][curr]; // Setting the state as solved v[i][curr] = true; // Recurrence relation return dp[i][curr] = findCnt(arr, i + 1, curr, n, m) + findCnt(arr, i + 1, (curr + arr[i]) % m, n, m);}// Driver codepublic static void main(String[] args){ int arr[] = { 3, 3, 3, 3 }; int n = arr.length; int m = 6; System.out.println(findCnt(arr, 0, 0, n, m) - 1);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approachmaxN = 20maxM = 10# To store the states of DPdp = [[0 for i in range(maxN)] for i in range(maxM)]v = [[0 for i in range(maxN)] for i in range(maxM)]# Function to find the required countdef findCnt(arr, i, curr, n, m): # Base case if (i == n): if (curr == 0): return 1 else: return 0 # If the state has been solved before # return the value of the state if (v[i][curr]): return dp[i][curr] # Setting the state as solved v[i][curr] = 1 # Recurrence relation dp[i][curr] = findCnt(arr, i + 1, curr, n, m) + \ findCnt(arr, i + 1, (curr + arr[i]) % m, n, m) return dp[i][curr]# Driver codearr = [3, 3, 3, 3]n = len(arr)m = 6print(findCnt(arr, 0, 0, n, m) - 1)# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System;class GFG { static int maxN = 20; static int maxM = 10; // To store the states of DP static int [,]dp = new int[maxN, maxM]; static bool [,]v = new bool[maxN, maxM]; // Function to find the required count static int findCnt(int[] arr, int i, int curr, int n, int m) { // Base case if (i == n) { if (curr == 0) return 1; else return 0; } // If the state has been solved before // return the value of the state if (v[i, curr]) return dp[i, curr]; // Setting the state as solved v[i, curr] = true; // Recurrence relation return dp[i, curr] = findCnt(arr, i + 1, curr, n, m) + findCnt(arr, i + 1, (curr + arr[i]) % m, n, m); } // Driver code public static void Main() { int []arr = { 3, 3, 3, 3 }; int n = arr.Length; int m = 6; Console.WriteLine(findCnt(arr, 0, 0, n, m) - 1); } }// This code is contributed by kanugargng |
Javascript
<script>// Javascript implementation of the approachvar maxN = 20var maxM = 10// To store the states of DPvar dp = Array.from(Array(maxN), () => Array(maxM));var v = Array.from(Array(maxN), () => Array(maxM));// Function to find the required countfunction findCnt(arr, i, curr, n, m){ // Base case if (i == n) { if (curr == 0) return 1; else return 0; } // If the state has been solved before // return the value of the state if (v[i][curr]) return dp[i][curr]; // Setting the state as solved v[i][curr] = 1; // Recurrence relation dp[i][curr] = findCnt(arr, i + 1, curr, n, m) + findCnt(arr, i + 1, (curr + arr[i]) % m, n, m); return dp[i][curr];}// Driver codevar arr = [3, 3, 3, 3];var n = arr.length;var m = 6;document.write( findCnt(arr, 0, 0, n, m) - 1);</script> |
7
Time Complexity : O(2^n) as it uses a recursive approach with a branching factor of 2 at each level of recursion.
Space complexity : O(n*m) as it uses a 2D array with n rows and m columns to store the states of the DP.
Another 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 + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a table DP of size n*m to store the solution of the subproblems.
- Initialize the table DP with base cases.
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP.
- Return the final solution stored in dp[0][0] – 1
Implementation :
C++
// C++ code for above approach#include <bits/stdc++.h>using namespace std;#define maxN 20#define maxM 10// Function to find the required countint findCnt(int arr[] , int n , int m){ int dp[n + 1][m]; // Initialize the base case for (int j = 0; j < m; j++) { dp[n][j] = (j == 0) ? 1 : 0; } // Fill the table using DP for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < m; j++) { dp[i][j] = dp[i + 1][j] + dp[i + 1][(j - arr[i] + m) % m]; } } // Print the final answer return dp[0][0] - 1; }//Driver Codeint main(){ int arr[] = { 3, 3, 3, 3 }; int n = sizeof(arr) / sizeof(int); int m = 6; // Function call cout << findCnt(arr, n , m); return 0;} |
Java
// Java code for above approachimport java.util.*;public class Main { // Function to find the required count public static int findCnt(int[] arr, int n, int m) { int[][] dp = new int[n + 1][m]; // Initialize the base case for (int j = 0; j < m; j++) { dp[n][j] = (j == 0) ? 1 : 0; } // Fill the table using DP for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < m; j++) { dp[i][j] = dp[i + 1][j] + dp[i + 1][(j - arr[i] + m) % m]; } } // Print the final answer return dp[0][0] - 1; } // Driver Code public static void main(String[] args) { int[] arr = { 3, 3, 3, 3 }; int n = arr.length; int m = 6; // Function call System.out.println(findCnt(arr, n, m)); } } |
Python3
# Python code for above approach# Function to find the required countdef findCnt(arr, n, m): dp = [[0 for j in range(m)] for i in range(n + 1)] # Initialize the base case for j in range(m): dp[n][j] = 1 if j == 0 else 0 # Fill the table using DP for i in range(n - 1, -1, -1): for j in range(m): dp[i][j] = dp[i + 1][j] + dp[i + 1][(j - arr[i] + m) % m] # Print the final answer return dp[0][0] - 1# Driver Codearr = [3, 3, 3, 3]n = len(arr)m = 6# Function callprint(findCnt(arr, n, m)) |
C#
// C# code for above approachusing System;class GFG { const int maxN = 20; const int maxM = 10; // Function to find the required count static int FindCnt(int[] arr, int n, int m) { int[, ] dp = new int[n + 1, m]; // Initialize the base case for (int j = 0; j < m; j++) { dp[n, j] = (j == 0) ? 1 : 0; } // Fill the table using DP for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < m; j++) { dp[i, j] = dp[i + 1, j] + dp[i + 1, (j - arr[i] + m) % m]; } } // Print the final answer return dp[0, 0] - 1; } // Driver Code static void Main() { int[] arr = { 3, 3, 3, 3 }; int n = arr.Length; int m = 6; // Function call Console.WriteLine(FindCnt(arr, n, m)); }} |
Javascript
// Function to find the required countfunction findCnt(arr, n, m) { let dp = new Array(n + 1); for (let i = 0; i < dp.length; i++) { dp[i] = new Array(m).fill(0); } // Initialize the base case for (let j = 0; j < m; j++) { dp[n][j] = j == 0 ? 1 : 0; } // Fill the table using DP for (let i = n - 1; i >= 0; i--) { for (let j = 0; j < m; j++) { dp[i][j] = dp[i + 1][j] + dp[i + 1][(j - arr[i] + m) % m]; } } // Print the final answer return dp[0][0] - 1;}// Driver Codelet arr = [3, 3, 3, 3];let n = arr.length;let m = 6;// Function callconsole.log(findCnt(arr, n, m)); |
Output
7
Time Complexity : O(n*m)
Auxiliary Space : O(n*m)
Efficient approach : Space optimization
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D vector dp of size m.
- Set a base case by initializing the value of DP ( dp[0] = 1 ).
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- Now create a temporary array next_dp to store the current values from previous computations.
- After every iteration assign the value of next_dp to dp for further iteration.
- At last return and print the final answer stored in dp[0]-1.
Implementation:
C++
// C++ code for above approach#include <bits/stdc++.h>using namespace std;// Function to find the required countint findCnt(int arr[], int n, int m){ int dp[m] = { 0 }; dp[0] = 1; // Fill the table using DP for (int i = 0; i < n; i++) { int next_dp[m]; for (int j = 0; j < m; j++) { next_dp[j] = dp[j] + dp[(j - arr[i] + m) % m]; } memcpy(dp, next_dp, sizeof(next_dp)); } // Print the final answer return dp[0] - 1;}// Driver Codeint main(){ int arr[] = { 3, 3, 3, 3 }; int n = sizeof(arr) / sizeof(int); int m = 6; // Function call cout << findCnt(arr, n, m); return 0;} |
Java
import java.util.Arrays;public class GFG { // Function to find the required count static int findCnt(int[] arr, int n, int m) { int[] dp = new int[m]; dp[0] = 1; // Fill the table using DP for (int i = 0; i < n; i++) { int[] next_dp = new int[m]; for (int j = 0; j < m; j++) { next_dp[j] = dp[j] + dp[(j - arr[i] + m) % m]; } dp = Arrays.copyOf(next_dp, m); } // Print the final answer return dp[0] - 1; } // Driver Code public static void main(String[] args) { int[] arr = { 3, 3, 3, 3 }; int n = arr.length; int m = 6; // Function call System.out.println(findCnt(arr, n, m)); }} |
Python
def findCnt(arr, n, m): dp = [0] * m dp[0] = 1 # Fill the table using DP for i in range(n): next_dp = [0] * m for j in range(m): next_dp[j] = dp[j] + dp[(j - arr[i] + m) % m] dp = next_dp # Print the final answer return dp[0] - 1# Driver Codeif __name__ == "__main__": arr = [3, 3, 3, 3] n = len(arr) m = 6 # Function call print(findCnt(arr, n, m)) |
C#
using System;class GFG { // Function to find the required count static int FindCnt(int[] arr, int n, int m) { int[] dp = new int[m]; dp[0] = 1; // Fill the table using DP for (int i = 0; i < n; i++) { int[] nextDp = new int[m]; for (int j = 0; j < m; j++) { nextDp[j] = dp[j] + dp[(j - arr[i] + m) % m]; } Array.Copy(nextDp, dp, m); } // Print the final answer return dp[0] - 1; } // Driver Code static void Main() { int[] arr = { 3, 3, 3, 3 }; int n = arr.Length; int m = 6; // Function call Console.WriteLine(FindCnt(arr, n, m)); }} |
Javascript
// Function to find the required countfunction findCnt(arr, n, m) { const dp = new Array(m).fill(0); dp[0] = 1; // Fill the table using DP for (let i = 0; i < n; i++) { const nextDp = new Array(m); for (let j = 0; j < m; j++) { nextDp[j] = dp[j] + dp[(j - arr[i] + m) % m]; } dp.splice(0, m, ...nextDp); } // Print the final answer return dp[0] - 1;}// Driver Codefunction main() { const arr = [3, 3, 3, 3]; const n = arr.length; const m = 6; // Function call console.log(findCnt(arr, n, m));}main(); |
7
Time Complexity : O(n*m)
Auxiliary Space : O(m)
METHOD 4:Using re
APPRAOCH:
The count_subsets function takes an array arr and a number m as inputs. It iterates over all possible subsets of arr using bit manipulation and checks if the sum of each subset is divisible by m. It keeps a count of such subsets and returns the final count
ALGORITHM:
1.Initialize a count variable to 0.
2.Get the length of the array arr and store it in n.
3.Iterate from 1 to 2^n – 1 (representing all possible subsets of arr).
4.For each iteration, generate a subset by checking the bits of the current iteration number i.
5.If the jth bit of i is set ((i >> j) & 1), include the corresponding element arr[j] in the subset.
6.Check if the sum of the subset is divisible by m using the modulo operator.
7.If it is, increment the count.
8.Return the final count.
Python3
import redef count_subsets(arr, m): count = 0 n = len(arr) for i in range(1, 2**n): subset = [arr[j] for j in range(n) if (i >> j) & 1] if sum(subset) % m == 0: count += 1 return countarr = [3, 3, 3, 3]m = 6result = count_subsets(arr, m)print(result) |
7
Time Complexity:
The time complexity of this approach is O(2^n * n), where n is the length of the array arr. Generating all possible subsets using bit manipulation takes O(2^n) time, and for each subset, we calculate the sum in O(n) time.
Auxiliary Space:
The space complexity is O(n), where n is the length of the array arr. We store the generated subset temporarily, and the space required is proportional to the number of elements in the array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
