Subset with sum divisible by m

Problem Statement

The problem “Subset with sum divisible by m” states that you are given an array of non-negative integers and an integer m. Now you need to find if there is a subset having sum divisible by m. That is the sum of the subset should give 0 as a result when we take its mode with m.

Example

array = {1, 2, 4}
m = 3

True

Explanation

Subset having values {1,2} sum to give 3 as result. {2, 4} also sum up to give 6 as a result which is also divisible by 3. Thus the answer is true.

Approach

So, we have also come across a similar problem which is to check if the sum of the subset is equal to a target Sum. But here do not check if the subset-sum is equal to a given sum but we need to check if the subset-sum is divisible by m. So we can reframe the problem as we need to find if there is a subset having sum = m, 2m, 3m, .., etc. If the subset has a sum equal to any of the given values. we return true else false.

So, instead of thinking this way. We keep on taking the mod of sum and if we somehow get a 0. We are sure that there exists a subset having sum divisible by m. But we need to care about something before that. If the number of elements n>=m(number against whose mod is to be taken). Then the answer always exists because of the Pigeonhole Principle. We only need to deal with cases having sum 0 to m-1 which is n<=m.

So, the whole idea behind this approach is that we have some subsets having sum = j, then we can create new subset having sum = (j+current_element)%m. And that’s how we are going to fill our Dynamic Programming Table.

Code

C++ code for Subset with sum divisible by m

#include<bits/stdc++.h>
using namespace std;

bool findSubsetDivisibleByM(int arr[], int n, int m)
{
  // because of piegonhole principle
  if (n > m)
    return true;

  // this will work as dp array for all elements until the last element
  bool dp[m]; memset(dp, false, m);

  for (int i=0; i<n; i++)
  {
    // this will work as our current dp array
    bool tmp[m]; memset(tmp,false,m);

    // we will add the current element to all possible subset sum
    // until now and then take the mod of the sum and will keep
    // on filling the current dp array(tmp)
    for (int j=0; j<m; j++)
    {
      // if the dp table until the last element has subset sum = j
      if (dp[j] == true)
      {
        if (dp[(j+arr[i]) % m] == false)
          // fill the current dp table(tmp array)
          tmp[(j+arr[i]) % m] = true;
      }
    }

    // now just fill the original dp array
    for (int j=0; j<m; j++)
      if (tmp[j] == true)
        dp[j] = true;
    // fill the dp array considering you have subset made of only current element
    dp[arr[i]%m] = true;
  }

  return dp[0];
}

int main(){
  // Number of elements
  int n;cin>>n;
  // Number which should divide the subset
  int m;cin>>m;
  // array to store non-negative numbers
  int a[n];
  for(int i=0;i<n;i++)
    cin>>a[i];
  bool can = findSubsetDivisibleByM(a, n, m);
  if(can == true)
    cout<<"There exists a subset having sum divisible by m";
  else
    cout<<"There does not exist any subset having sum divisible by m";
}

3 3 
1 2 4

There exists a subset having sum divisible by m

Java code for Subset with sum divisible by m

import java.util.*;
class Main{
  
  	static boolean findSubsetDivisibleByM(int arr[], int n, int m)
  {
    // because of piegonhole principle
    if (n > m)
      return true;

    // this will work as dp array for all elements until the last element
    boolean dp[] = new boolean [m];
    for(int i=0;i<m;i++)
      dp[i] = false;

    for (int i=0;i<n; i++)
    {
      // this will work as our current dp array
      boolean tmp[] = new boolean[m];
      for(int j=0;j<m;j++)
        tmp[j] = false;
      // we will add the current element to all possible subset sum
      // until now and then take the mod of the sum and will keep
      // on filling the current dp array(tmp)
      for (int j=0; j<m; j++)
      {
        // if the dp table until the last element has subset sum = j
        if (dp[j] == true)
        {
          if (dp[(j+arr[i]) % m] == false)
            // fill the current dp table(tmp array)
            tmp[(j+arr[i]) % m] = true;
        }
      }

      // now just fill the original dp array
      for (int j=0; j<m; j++)
        if (tmp[j] == true)
          dp[j] = true;
      // fill the dp array considering you have subset made of only current element
      dp[arr[i]%m] = true;
    }

    return dp[0];
  }
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    // Number of elements
    int n = sc.nextInt();
    int m = sc.nextInt();
    // array to store non-negative numbers
    int a[] = new int[n];
    for(int i=0;i<n;i++)
      a[i] = sc.nextInt();
    boolean can = findSubsetDivisibleByM(a, n, m);
    if(can == true)
      System.out.println("There exists a subset having sum divisible by m");
    else
      System.out.println("There does not exist any subset having sum divisible by m");
  	}
}

3 3
1 2 4

There exists a subset having sum divisible by m

Complexity Analysis

Time Complexity

O(M^2), because we have to solve the problem only when n<=m. Thus the upper bound for n is m. Thus the time complexity is polynomial.

Space Complexity

O(M), because the space required for the dp array is linear. Space was only required for storing the dp table and thus the space complexity is linear.