Find if a Subset with sum divisible by m exist
Reading time: 30 minutes  Coding time: 10 minutes
In this problem we will be given an array of size n and a number m and we have to find whether there exists a subset with sum divisble by m.
Example
Consider the following set S:
{ 2, 4, 6, 11, 2}
There exists no subset which is divisible by 7
At the same time, we have multiple subsets that is divisible by 4
{2, 2} {4} {2, 4, 2} {2, 6} {2, 4, 6}
We solve this using two approaches:
 Naive algorithm O(2^N)
 Dynamic Programming O(N * M)
Naive Algorithm
Basic Idea:
Generate all possible subset sum using recursion or iteratively and check if the current sum is divisble by m.If we visualize this method,by making a recursive tree we see that there will be redundant cases and thus the complexity is exponential.
Pseudo Code of Naive algorithm
void subsetSums(int arr[], int l, int r,
int sum=0)
{
// Check current subset
if (l > r)
{
if(sum%m==0&&sum!=0)
return true;
}
// Subset including arr[l]
subsetSums(arr, l+1, r, sum+arr[l]);
// Subset excluding arr[l]
subsetSums(arr, l+1, r, sum);
return false;
}
Time Complexity
Since we generate all possible subset sums, and there are 2^n subsets in totality, therefore complexity of the naive algorithm is O(2^n) where n is the number of elements in the array.
Efficient Algorithm using Dynamic Programming
Basic Idea:
We will use Dynamic Programming approach to solve this problem efficiently.
Here we take two cases:

n>mFor all such cases, there will always be a subset divisble by m which we can easily prove by using pigeonhole principle.

n<=m: For all such cases we create an array DP[] of size m which is of type bool . We initialize that array with false. This array gives the status of all possible sum modulo m.
DP[i] = true if subset with sum S modulo m = i exists
We use another array temp store all the new encountered sum (after modulo). It is used to make sure that arr[i] is added only to those entries for which DP[j] was true before current iteration.
Algorithm
We loop through all the elements in the given array and for each element arr[i] we check that if DP[j]==true we mark DP[(j+arr[i]) modulo m]=true and temp[(j+arr[i]) modulo m]=true which denotes that a subset with sum exist whose modulus with m gives the value j.
if DP[j] == true and for each arr[i]
set DP[ (j+arr[i])%m ] = true
set temp[ (j+arr[i])%m ] = true
After that we update the DP[j]=true if temp[j]=true. In the beginnning of every iteration we check if DP[0]=true, if that is the case we return true which means a subset sum exists whose modulus with m gives the value 0.
if temp[i] = true
set DP[i] = true
DP[0] is our answer
Pseudo Code:
boolSubsetSum(int arr[])
{
initialize DP[] with false;
if(DP[0]==true)
return true;
for(i=0;i<size;i++)
{
initialize temp[] with false;
for(j=0;j<m;j++)
{
if(DP[j]==true)
{
if(DP[(j+arr[i])%m]==false)
{
temp[(j+arr[i])%m]=true;
}
}
}
for(i=0;i<m;i++)
{
if(temp[j]==true)
DP[j]=true;
}
DP[arr[i]%m] = true;
}
return DP[0];
}
C++ Implementation:
Following is the C++ implementation:
#include <bits/stdc++.h>
using namespace std;
bool modularSum(int arr[], int n, int m)
{
//According to Pigeonhole Principle
if (n > m)
return true;
//DP[] array keeps track of all possible
//subset sum modulo m
bool DP[m];
memset(DP, false, m);
for (int i=0; i<n; i++)
{
//if DP[0]==true that means
//A subset with sum divisible by m exists
if (DP[0])
return true;
// To store all the new encountered sum (after
// modulo). It is used to make sure that arr[i]
// is added only to those entries for which DP[j]
// was true before current iteration.
bool temp[m];
memset(temp,false,m);
//For each element in arr[] we find if
//DP[j] exists and calculate next possible
//value of sum modulus m
for (int j=0; j<m; j++)
{
if (DP[j] == true)
{
if (DP[(j+arr[i]) % m] == false)
//Update temp
temp[(j+arr[i]) % m] = true;
}
}
// Updating all the elements of temp to DP
for (int j=0; j<m; j++)
if (temp[j])
DP[j] = true;
//Since single element sum is also possible
DP[arr[i]%m] = true;
}
return DP[0];
}
int main()
{
int arr[] = {2,4,2,1,5};
int n = sizeof(arr)/sizeof(arr[0]);
int m = 9;
modularSum(arr, n, m) ? cout << "YES\n" :
cout << "NO\n";
return 0;
}
Output:
YES
Time Complexity:
Since the outer loop is executing n times and for each iteration of outer loop, the inner loop executes m times, the complexity becomes O(nm) where n is the number of array elements and m is the divisor.
Happy Coding!