Number of subsets with sum divisible by M | Set 2

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:  

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 :

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: 

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.

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.