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-:

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!