Open In App

Subset with sum divisible by m

Last Updated : 06 Feb, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

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(2N)

Auxiliary Space: O(2N)

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)

 



Similar Reads

Find a non empty subset in an array of N integers such that sum of elements of subset is divisible by N
Given an array of N integers, the task is to find a non-empty subset such that the sum of elements of the subset is divisible by N. Output any such subset with its size and the indices(1-based indexing) of elements in the original array if it exists. Prerequisites: Pigeonhole PrincipleExamples: Input: arr[] = { 2, 3, 7, 1, 9 } Output: 2 1 2 The req
8 min read
Sum of maximum and minimum of Kth subset ordered by increasing subset sum
Given an integer N and a set of all non-negative powers of N as S = {N0, N1, N2, N3, ... }, arrange all non-empty subsets of S in increasing order of subset-sum. The task is to find the sum of the greatest and smallest elements of the Kth subset from that ordering. Examples: Input: N = 4, K = 3Output: 5Explanation: S = {1, 4, 16, 64, ...}.Therefore
7 min read
Find maximum subset sum formed by partitioning any subset of array into 2 partitions with equal sum
Given an array A containing N elements. Partition any subset of this array into two disjoint subsets such that both the subsets have an identical sum. Obtain the maximum sum that can be obtained after partitioning. Note: It is not necessary to partition the entire array, that is any element might not contribute to any of the partition. Examples: In
15+ min read
Split Array into K non-overlapping subset such that maximum among all subset sum is minimum
Given an array arr[] consisting of N integers and an integer K, the task is to split the given array into K non-overlapping subsets such that the maximum among the sum of all subsets is minimum. Examples: Input: arr[] = {1, 7, 9, 2, 12, 3, 3}, M = 3Output: 13Explanation:One possible way to split the array into 3 non-overlapping subsets is {arr[4],
7 min read
Minimum Subset sum difference problem with Subset partitioning
Given a set of N integers with up to 40 elements, the task is to partition the set into two subsets of equal size (or the closest possible), such that the difference between the sums of the subsets is minimized. If the size of the set is odd, one subset will have one more element than the other. If the size is even, both subsets will have the same
13 min read
Largest possible Subset from an Array such that no element is K times any other element in the Subset
Given an array arr[] consisting of N distinct integers and an integer K, the task is to find the maximum size of a subset possible such that no element in the subset is K times any other element of the subset(i.e. no such pair {n, m} should be present in the subset such that either m = n * K or n = m * K). Examples: Input: arr[] = {2, 8, 6, 5, 3},
7 min read
Maximum size of subset such that product of all subset elements is a factor of N
Given an integer N and an array arr[] having M integers, the task is to find the maximum size of the subset such that the product of all elements of the subset is a factor of N. Examples: Input: N = 12, arr[] = {2, 3, 4}Output: 2Explanation: The given array 5 subsets such that the product of all elements of the subset is a factor of 12. They are {2
6 min read
Find maximum subset-sum divisible by D by taking at most K elements from given array
Given an array A[] of size N, and two numbers K and D, the task is to calculate the maximum subset-sum divisible by D possible by taking at most K elements from A. Examples: Input: A={11, 5, 5, 1, 18}, N=5, K=3, D=7Output:28Explanation:The subset {5, 5, 18} gives the maximum sum=(5+5+18)=28 that is divisible by 7 and also has contains atmost 3 elem
11 min read
Subset with no pair sum divisible by K
Given an array of integer numbers, we need to find maximum size of a subset such that sum of each pair of this subset is not divisible by K. Examples : Input : arr[] = [3, 7, 2, 9, 1] K = 3 Output : 3 Maximum size subset whose each pair sum is not divisible by K is [3, 7, 1] because, 3+7 = 10, 3+1 = 4, 7+1 = 8 all are not divisible by 3. It is not
7 min read
Size of the largest divisible subset in an Array
Given an array arr[] of size N. The task is to find the size of the set of numbers from the given array such that each number divides another or is divisible by another.Examples: Input : arr[] = {3, 4, 6, 8, 10, 18, 21, 24} Output : 3 One of the possible sets with a maximum size is {3, 6, 18} Input : arr[] = {2, 3, 4, 8, 16} Output : 4 Approach: Le
5 min read