×

Search anything:

Find if a Subset with sum divisible by m exist

Algorithms Dynamic Programming (DP)

Get this book -> Problems on Array: For Interviews and Competitive Programming

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.

Basic Idea-:

We will use Dynamic Programming approach to solve this problem efficiently.

Here we take two cases-:

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

2. 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!

Siddharth Agarwal

Intern at OpenGenus | Bachelor of Technology (2017 to 2021) in Computer Science at Institute of Engineering and Technology

Improved & Reviewed by:

Find if a Subset with sum divisible by m exist