Subset with sum divisible by m

Last Updated : 06 Feb, 2023

Given a set of non-negative distinct integers, and a value m, determine if there is a subset of the given set with sum divisible by m.
Input Constraints
Size of set i.e., n <= 1000000, m <= 1000
Examples:

Input : arr[] = {3, 1, 7, 5};
        m = 6;
Output : YES

Input : arr[] = {1, 6};
        m = 5;
Output : NO

This problem is a variant of subset sum problem. In subset sum problem we check if given sum subset exists or not, here we need to find if there exists some subset with sum divisible by m or not.

Naive Approach( Using Recursion) :

C++

// C++ program to check if there is a subset
// with sum divisible by m.
#include <bits/stdc++.h>
using namespace std;
 
// Returns true if there is a subset
// of arr[] with sum divisible by m
bool helper(int N, int nums[], int sum, int idx, int m){
    // if we reach last index
    if(idx == N){
        // and if the sum mod m is zero
        if(sum && sum%m == 0){
            // return
              return true ;
        }
        return false ;
    }
 
    // 2 choices - to pick or to not pick
    bool picked    = helper(N, nums, sum+nums[idx], idx+1,m) ;
    bool notPicked = helper(N, nums, sum,          idx+1, m) ;
 
    return picked || notPicked ;
}
 
bool modularSum(int arr[], int n, int m)
{
    return helper(n, arr, 0, 0, m) ;
}
 
// Driver code
int main()
{
    int arr[] = {1, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    int m = 5;
 
    modularSum(arr, n, m) ?  cout << "YES\n" :
                             cout << "NO\n";
 
    return 0;
}

Java

// Java program to check if there is a subset
// with sum divisible by m.
 
class GFG {
 
  // Returns true if there is a subset
  // of arr[] with sum divisible by m
  public static boolean helper(int N, int[] nums, int sum,
                               int idx, int m)
  {
    // if we reach last index
    if (idx == N) 
    {
 
      // and if the sum mod m is zero
      if ((sum > 0) && (sum % m == 0)) {
        // return
        return true;
      }
      return false;
    }
 
    // 2 choices - to pick or to not pick
    boolean picked
      = helper(N, nums, sum + nums[idx], idx + 1, m);
    boolean notPicked
      = helper(N, nums, sum, idx + 1, m);
 
    return picked || notPicked;
  }
 
  public static boolean modularSum(int[] arr, int n,
                                   int m)
  {
    return helper(n, arr, 0, 0, m);
  }
 
  // driver code
  public static void main(String[] args)
  {
    int arr[] = { 1, 7 };
    int n = arr.length;
    int m = 5;
 
    if (modularSum(arr, n, m))
      System.out.print("YES\n");
    else
      System.out.print("NO\n");
  }
}
 
// this code is contributed by phasing17

Python3

# Python3 program to check if there is a subset
# with sum divisible by m.
 
# Returns true if there is a subset
# of arr[] with sum divisible by m
def helper(N, nums, sum, idx, m):
 
    # if we reach last index
    if(idx == N):
     
        # and if the sum mod m is zero
        if(sum and sum%m == 0):
 
            # return
            return True
     
        return False
 
    # 2 choices - to pick or to not pick
    picked    = helper(N, nums, sum+nums[idx], idx+1,m)
    notPicked = helper(N, nums, sum,          idx+1, m)
 
    return picked or notPicked
 
def modularSum(arr, n, m):
    return helper(n, arr, 0, 0, m) 
 
# Driver code
arr = [1, 7]
n = len(arr)
m = 5
 
print("YES") if modularSum(arr, n, m) else print("NO")
 
# This code is contributed by shinjanpatra.

C#

// C# program to check if there is a subset
// with sum divisible by m.
using System;
 
class GFG {
 
  // Returns true if there is a subset
  // of arr[] with sum divisible by m
  public static bool helper(int N, int[] nums, int sum,
                            int idx, int m)
  {
    // if we reach last index
    if (idx == N) {
 
      // and if the sum mod m is zero
      if ((sum > 0) && (sum % m == 0)) {
        // return
        return true;
      }
      return false;
    }
 
    // 2 choices - to pick or to not pick
    bool picked
      = helper(N, nums, sum + nums[idx], idx + 1, m);
    bool notPicked = helper(N, nums, sum, idx + 1, m);
 
    return picked || notPicked;
  }
 
  public static bool modularSum(int[] arr, int n, int m)
  {
    return helper(n, arr, 0, 0, m);
  }
 
  // driver code
  public static void Main(string[] args)
  {
    int[] arr = { 1, 7 };
    int n = arr.Length;
    int m = 5;
 
    if (modularSum(arr, n, m))
      Console.Write("YES\n");
    else
      Console.Write("NO\n");
  }
}
 
// this code is contribyted by phasing17

Javascript

<script>
 
// JavaScript program to check if there is a subset
// with sum divisible by m.
 
// Returns true if there is a subset
// of arr[] with sum divisible by m
function helper(N, nums, sum, idx, m)
{
 
    // if we reach last index
    if(idx == N)
    {
     
        // and if the sum mod m is zero
        if(sum && sum%m == 0)
        {
         
            // return
              return true ;
        }
        return false ;
    }
 
    // 2 choices - to pick or to not pick
    let picked    = helper(N, nums, sum+nums[idx], idx+1,m) ;
    let notPicked = helper(N, nums, sum,          idx+1, m) ;
 
    return picked || notPicked ;
}
 
function modularSum(arr, n, m)
{
    return helper(n, arr, 0, 0, m) ;
}
 
// Driver code
 
let arr = [1, 7];
let n = arr.length;
let m = 5;
 
modularSum(arr, n, m) ?  document.write("YES","</br>") : document.write("NO","</br>");
 
// This code is contributed by shinjanpatra.
</script>

Output

NO

Time Complexity: O(2^N)

Auxiliary Space: O(2^N)

Memoization Approach: As this contains overlapping subproblems so instead of calling the same function again and again we will store it in a 2D array.
It follows the recursive approach but in this method, we use a 2D matrix that is initialized by -1 or any negative value.
The 2D matrix is used for memorization purpose to avoid repeated recursive calls from the same state.

Below is the implementation of the approach.

C++

// C++ program to check if there is a subset
// with sum divisible by m.
 
#include <bits/stdc++.h>
using namespace std;
 
// Returns true if there is a subset
// of arr[] with sum divisible by m
bool helper(int N, int nums[], int sum, int idx, 
            int m, vector<vector<int> >& dp)
{
    // if we reach last index
    if (idx == N) {
        // and if the sum mod m is zero
        if (sum && sum % m == 0) {
            // return
            return true;
        }
        return false;
    }
    if (dp[idx][sum] != -1) {
        return dp[idx][sum];
    }
   
    // 2 choices - to pick or to not pick
    bool picked
        = helper(N, nums, sum + nums[idx], 
                 idx + 1, m, dp);
    bool notPicked = helper(N, nums, sum, 
                            idx + 1, m, dp);
 
    return dp[idx][sum] = picked || notPicked;
}
 
bool modularSum(int arr[], int n, int m)
{
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    vector<vector<int> > dp(n, vector<int>(sum + 1, 
                                           -1));
 
    return helper(n, arr, 0, 0, m, dp);
}
 
// Driver code
int main()
{
    int arr[] = { 1, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 5;
 
    modularSum(arr, n, m) ? cout << "YES\n"
                          : cout << "NO\n";
 
    return 0;
}
// This code is contributed by Sanskar

Java

// Java program to check if there is a subset
// with sum divisible by m.
 
import java.util.Arrays;
class GFG {
 
    // Returns true if there is a subset
    // of arr[] with sum divisible by m
    public static boolean helper(int N, int[] nums, int sum,
                                 int idx, int m, int dp[][])
    {
        // if we reach last index
        if (idx == N) {
 
            // and if the sum mod m is zero
            if ((sum > 0) && (sum % m == 0)) {
                // return
                return true;
            }
            return false;
        }
        if (dp[idx][sum] != -1) {
            return dp[idx][sum] == 0 ? false : true;
        }
        // 2 choices - to pick or to not pick
        boolean picked = helper(N, nums, sum + nums[idx],
                                idx + 1, m, dp);
        boolean notPicked
            = helper(N, nums, sum, idx + 1, m, dp);
 
        dp[idx][sum] = notPicked || picked ? 1 : 0;
        return notPicked || picked;
    }
 
    public static boolean modularSum(int[] arr, int n,
                                     int m)
    {
 
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += arr[i];
        }
        int dp[][] = new int[n][sum + 1];
        for (int row[] : dp) {
            Arrays.fill(row, -1);
        }
 
        return helper(n, arr, 0, 0, m, dp);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 1, 7 };
        int n = arr.length;
        int m = 5;
 
        if (modularSum(arr, n, m))
            System.out.print("YES\n");
        else
            System.out.print("NO\n");
    }
}
 
// This code is contributed by Sanskar

Python3

# Python program to check if there is a subset
# with sum divisible by m.
 
# Returns true if there is a subset
# of arr[] with sum divisible by m
def helper(N, nums, sum, idx, m, dp):
   
    # if we reach last index
    if idx == N:
       
        # and if the sum mod m is zero
        if sum and sum % m == 0:
            # return
            return True
        return False
    if dp[idx][sum] != -1:
        return dp[idx][sum]
   
    # 2 choices - to pick or to not pick
    picked = helper(N, nums, sum + nums[idx], idx + 1, m, dp)
    notPicked = helper(N, nums, sum, idx + 1, m, dp)
 
    dp[idx][sum] = picked or notPicked
    return dp[idx][sum]
 
def modularSum(arr, n, m):
    sum = 0
    for i in range(n):
        sum += arr[i]
    dp = [[-1] * (sum + 1) for i in range(n)]
 
    return helper(n, arr, 0, 0, m, dp)
 
# Driver code
arr = [1, 7]
n = len(arr)
m = 5
 
print("YES") if modularSum(arr, n, m) else print("NO")
 
# This code is contributed by phasing17

C#

// C# program to check if there is a subset
// with sum divisible by m.
 
using System;
using System.Collections.Generic;
 
class GFG {
 
    // Returns true if there is a subset
    // of arr[] with sum divisible by m
    public static bool helper(int N, int[] nums, int sum,
                              int idx, int m, int[][] dp)
    {
        // if we reach last index
        if (idx == N) {
 
            // and if the sum mod m is zero
            if ((sum > 0) && (sum % m == 0)) {
                // return
                return true;
            }
            return false;
        }
        if (dp[idx][sum] != -1) {
            return dp[idx][sum] == 0 ? false : true;
        }
        // 2 choices - to pick or to not pick
        bool picked = helper(N, nums, sum + nums[idx],
                             idx + 1, m, dp);
        bool notPicked
            = helper(N, nums, sum, idx + 1, m, dp);
 
        dp[idx][sum] = notPicked || picked ? 1 : 0;
        return notPicked || picked;
    }
 
    public static bool modularSum(int[] arr, int n, int m)
    {
 
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += arr[i];
        }
        int[][] dp = new int[n][];
        for (int i = 0; i < n; i++) {
            dp[i] = new int[sum + 1];
            Array.Fill(dp[i], -1);
        }
 
        return helper(n, arr, 0, 0, m, dp);
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int[] arr = { 1, 7 };
        int n = arr.Length;
        int m = 5;
 
        // Function call
        if (modularSum(arr, n, m))
            Console.Write("YES\n");
        else
            Console.Write("NO\n");
    }
}
 
// This code is contributed by phasing17

Javascript

<script>
 
// JavaScript program to check if there is a subset
// with sum divisible by m.
 
 
// Returns true if there is a subset
// of arr[] with sum divisible by m
function helper(N, nums, sum, idx, m, dp)
{
    // if we reach last index
    if (idx == N) {
        // and if the sum mod m is zero
        if (sum && sum % m == 0) {
            // return
            return true;
        }
        return false;
    }
    if (dp[idx][sum] != -1) {
        return dp[idx][sum];
    }
   
    // 2 choices - to pick or to not pick
    let picked
        = helper(N, nums, sum + nums[idx], 
                 idx + 1, m, dp);
    let notPicked = helper(N, nums, sum, 
                            idx + 1, m, dp);
 
    return dp[idx][sum] = picked || notPicked;
}
 
function modularSum(arr, n, m)
{
    let sum = 0;
    for (let i = 0; i < n; i++) {
        sum += arr[i];
    }
    let dp = new Array(n).fill(0).map(()=>new Array(sum + 1).fill(-1));
 
    return helper(n, arr, 0, 0, m, dp);
}
 
// Driver code
 
let arr = [ 1, 7 ];
let n = arr.length;
let m = 5;
 
modularSum(arr, n, m) ? document.write("YES","</br>")
                          : document.write("NO","</br>");
 
// This code is contributed by shinjanpatra
 
</script>

Output

NO

Time Complexity: O(N*sum) where sum is the sum of the array elements.
Auxiliary Space: O(N*sum)

Efficient Approach:

Seeing input constraint, it looks like typical DP solution will work in O(nm) time. But in tight time limits in competitive programming, the solution may work. Also auxiliary space is high for DP table, but here is catch.
If n > m there will always be a subset with sum divisible by m (which is easy to prove with pigeonhole principle). So we need to handle only cases of n <= m .
For n <= m we create a boolean DP table which will store the status of each value from 0 to m-1 which are possible subset sum (modulo m) which have been encountered so far.
Now we loop through each element of given array arr[], and we add (modulo m) j which have DP[j] = true, and store all the such (j+arr[i])%m possible subset-sum in a boolean array temp, and at the end of iteration over j, we update DP table with temp. Also we add arr[i] to DP ie.. DP[arr[i]%m] = true.
In the end if DP[0] is true then it means YES there exists a subset with sum which is divisible by m, else NO.

C++

// C++ program to check if there is a subset
// with sum divisible by m.
#include <bits/stdc++.h>
using namespace std;
 
// Returns true if there is a subset
// of arr[] with sum divisible by m
bool modularSum(int arr[], int n, int m)
{
    if (n > m)
        return true;
 
    // This array will keep track of all
    // the possible sum (after modulo m)
    // which can be made using subsets of arr[]
    // initialising boolean array with all false
    bool DP[m];
    memset(DP, false, m);
 
    // we'll loop through all the elements of arr[]
    for (int i=0; i<n; i++)
    {
        // anytime we encounter a sum divisible
        // by m, we are done
        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 of arr[], we loop through
        // all elements of DP table from 1 to m and
        // we add current element i. e., arr[i] to
        // all those elements which are true in DP
        // table
        for (int j=0; j<m; j++)
        {
            // if an element is true in DP table
            if (DP[j] == true)
            {
                if (DP[(j+arr[i]) % m] == false)
 
                    // We update it in temp and update
                    // to DP once loop of j is over
                    temp[(j+arr[i]) % m] = true;
            }
        }
 
        // Updating all the elements of temp
        // to DP table since iteration over
        // j is over
        for (int j=0; j<m; j++)
            if (temp[j])
                DP[j] = true;
 
 
        // Also since arr[i] is a single element
        // subset, arr[i]%m is one of the possible
        // sum
        DP[arr[i]%m] = true;
    }
 
    return DP[0];
}
 
// Driver code
int main()
{
    int arr[] = {1, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    int m = 5;
 
    modularSum(arr, n, m) ?  cout << "YES\n" :
                             cout << "NO\n";
 
    return 0;
}

Java

// Java program to check if there is a subset
// with sum divisible by m.
import java.util.Arrays;
 
class GFG {
     
    // Returns true if there is a subset
    // of arr[] with sum divisible by m
    static boolean modularSum(int arr[], 
                                int n, int m)
    {
        if (n > m)
            return true;
     
        // This array will keep track of all
        // the possible sum (after modulo m)
        // which can be made using subsets of arr[]
        // initialising boolean array with all false
        boolean DP[]=new boolean[m];
         
        Arrays.fill(DP, false);
     
        // we'll loop through all the elements
        // of arr[]
        for (int i = 0; i < n; i++)
        {
             
            // anytime we encounter a sum divisible
            // by m, we are done
            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. 
            boolean temp[] = new boolean[m];
            Arrays.fill(temp, false);
     
            // For each element of arr[], we loop 
            // through all elements of DP table 
            // from 1 to m and we add current 
            // element i. e., arr[i] to all those 
            // elements which are true in DP table
            for (int j = 0; j < m; j++)
            {
                 
                // if an element is true in 
                // DP table
                if (DP[j] == true)
                {
                    if (DP[(j + arr[i]) % m] == false)
     
                        // We update it in temp and update
                        // to DP once loop of j is over
                        temp[(j + arr[i]) % m] = true;
                }
            }
     
            // Updating all the elements of temp
            // to DP table since iteration over
            // j is over
            for (int j = 0; j < m; j++)
                if (temp[j])
                    DP[j] = true;
     
     
            // Also since arr[i] is a single 
            // element subset, arr[i]%m is one 
            // of the possible sum
            DP[arr[i] % m] = true;
        }
     
        return DP[0];
    }
     
    //driver code
    public static void main(String arg[])
    {
        int arr[] = {1, 7};
        int n = arr.length;
        int m = 5;
     
        if(modularSum(arr, n, m))
            System.out.print("YES\n");
        else
            System.out.print("NO\n");
    }
}
 
//This code is contributed by Anant Agarwal.

Python3

# Python3 program to check if there is 
# a subset with sum divisible by m.
 
# Returns true if there is a subset
# of arr[] with sum divisible by m
def modularSum(arr, n, m):
 
    if (n > m):
        return True
 
    # This array will keep track of all
    # the possible sum (after modulo m)
    # which can be made using subsets of arr[]
    # initialising boolean array with all false
    DP = [False for i in range(m)]
 
    # we'll loop through all the elements of arr[]
    for i in range(n):
     
        # anytime we encounter a sum divisible
        # by m, we are done
        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. 
        temp = [False for i in range(m)]
 
        # For each element of arr[], we loop through
        # all elements of DP table from 1 to m and
        # we add current element i. e., arr[i] to
        # all those elements which are true in DP
        # table
        for j in range(m):
         
            # if an element is true in DP table
            if (DP[j] == True):
             
                if (DP[(j + arr[i]) % m] == False):
 
                    # We update it in temp and update
                    # to DP once loop of j is over
                    temp[(j + arr[i]) % m] = True
             
        # Updating all the elements of temp
        # to DP table since iteration over
        # j is over
        for j in range(m):
            if (temp[j]):
                DP[j] = True
 
        # Also since arr[i] is a single element
        # subset, arr[i]%m is one of the possible
        # sum
        DP[arr[i] % m] = True
     
    return DP[0]
 
# Driver code
arr = [1, 7]
n = len(arr)
m = 5
print("YES") if(modularSum(arr, n, m)) else print("NO")
 
# This code is contributed by Anant Agarwal.

C#

// C# program to check if there is
// a subset with sum divisible by m.
using System;
 
class GFG {
     
// Returns true if there is a subset
// of arr[] with sum divisible by m
static bool modularSum(int []arr, int n,
                                  int m)
{
    if (n > m)
        return true;
  
    // This array will keep track of all
    // the possible sum (after modulo m)
    // which can be made using subsets of arr[]
    // initialising boolean array with all false
    bool []DP=new bool[m];
    for (int l=0;l<DP.Length;l++)
        DP[l]=false;
  
    // we'll loop through all the elements of arr[]
    for (int i=0; i<n; i++)
    {
        // anytime we encounter a sum divisible
        // by m, we are done
        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=new bool[m];
        for (int l=0;l<temp.Length;l++)
        temp[l]=false;
  
        // For each element of arr[], we loop through
        // all elements of DP table from 1 to m and
        // we add current element i. e., arr[i] to
        // all those elements which are true in DP
        // table
        for (int j=0; j<m; j++)
        {
            // if an element is true in DP table
            if (DP[j] == true)
            {
                if (DP[(j+arr[i]) % m] == false)
  
                    // We update it in temp and update
                    // to DP once loop of j is over
                    temp[(j+arr[i]) % m] = true;
            }
        }
  
        // Updating all the elements of temp
        // to DP table since iteration over
        // j is over
        for (int j=0; j<m; j++)
            if (temp[j])
                DP[j] = true;
  
  
        // Also since arr[i] is a single element
        // subset, arr[i]%m is one of the possible
        // sum
        DP[arr[i]%m] = true;
    }
  
    return DP[0];
}
 
//driver code
public static void Main()
{ 
     int []arr = {1, 7};
    int n = arr.Length;
    int m = 5;
 
    if(modularSum(arr, n, m))
    Console.Write("YES\n");
    else
    Console.Write("NO\n");
}
}
 
//This code is contributed by Anant Agarwal.

PHP

<?php
// Php program to check if there is a 
// subset with sum divisible by m. 
 
// Returns true if there is a subset 
// of arr[] with sum divisible by m 
function modularSum($arr, $n, $m) 
{ 
    if ($n > $m) 
        return true; 
 
    // This array will keep track of all 
    // the possible sum (after modulo m) 
    // which can be made using subsets of arr[] 
    // initialising boolean array with all false 
    $DP = Array_fill(0, $m, false);
 
    // we'll loop through all the elements of arr[] 
    for ($i = 0; $i < $n; $i++) 
    { 
        // anytime we encounter a sum divisible 
        // by m, we are done 
        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. 
        $temp = array_fill(0, $m, false) ;
 
        // For each element of arr[], we loop through 
        // all elements of DP table from 1 to m and 
        // we add current element i. e., arr[i] to 
        // all those elements which are true in DP 
        // table 
        for ($j = 0; $j < $m; $j++) 
        { 
            // if an element is true in DP table 
            if ($DP[$j] == true) 
            { 
                if ($DP[($j + $arr[$i]) % $m] == false) 
 
                    // We update it in temp and update 
                    // to DP once loop of j is over 
                    $temp[($j + $arr[$i]) % $m] = true; 
            } 
        } 
 
        // Updating all the elements of temp 
        // to DP table since iteration over 
        // j is over 
        for ($j = 0; $j < $m; $j++) 
            if ($temp[$j]) 
                $DP[$j] = true; 
 
        // Also since arr[i] is a single element 
        // subset, arr[i]%m is one of the possible 
        // sum 
        $DP[$arr[$i] % $m] = true; 
    } 
 
    return $DP[0]; 
} 
 
// Driver Code
$arr = array(1, 7); 
$n = sizeof($arr); 
$m = 5; 
 
if (modularSum($arr, $n, $m) == true )
    echo "YES\n";
else
    echo "NO\n"; 
 
// This code is contributed by Ryuga
?>

Javascript

<script>
 
    // JavaScript program to check if there is
    // a subset with sum divisible by m.
     
    // Returns true if there is a subset
    // of arr[] with sum divisible by m
    function modularSum(arr, n, m)
    {
        if (n > m)
            return true;
 
        // This array will keep track of all
        // the possible sum (after modulo m)
        // which can be made using subsets of arr[]
        // initialising boolean array with all false
        let DP = new Array(m);
        for (let l=0;l<m;l++)
            DP[l]=false;
 
        // we'll loop through all the elements of arr[]
        for (let i=0; i<n; i++)
        {
            // anytime we encounter a sum divisible
            // by m, we are done
            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.  
            let temp=new Array(m);
            for (let l=0;l<m;l++)
                temp[l]=false;
 
            // For each element of arr[], we loop through
            // all elements of DP table from 1 to m and
            // we add current element i. e., arr[i] to
            // all those elements which are true in DP
            // table
            for (let j=0; j<m; j++)
            {
                // if an element is true in DP table
                if (DP[j] == true)
                {
                    if (DP[(j+arr[i]) % m] == false)
 
                        // We update it in temp and update
                        // to DP once loop of j is over
                        temp[(j+arr[i]) % m] = true;
                }
            }
 
            // Updating all the elements of temp
            // to DP table since iteration over
            // j is over
            for (let j=0; j<m; j++)
                if (temp[j])
                    DP[j] = true;
 
 
            // Also since arr[i] is a single element
            // subset, arr[i]%m is one of the possible
            // sum
            DP[arr[i]%m] = true;
        }
 
        return DP[0];
    }
     
    let arr = [1, 7];
    let n = arr.length;
    let m = 5;
   
    if(modularSum(arr, n, m))
        document.write("YES" + "</br>");
    else
        document.write("NO" + "</br>");
     
</script>

Output

NO

Time Complexity : O(m^2)
Auxiliary Space : O(m)

Pratik Chhajer

Improve

Number of subsets with sum divisible by m

Subset with sum divisible by m

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

PHP

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?