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 mbool 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 codeint 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 mdef 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 notPickeddef modularSum(arr, n, m): return helper(n, arr, 0, 0, m) # Driver codearr = [1, 7]n = len(arr)m = 5print("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 mfunction 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 codelet 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 mbool 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 codeint 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 mdef 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 codearr = [1, 7]n = len(arr)m = 5print("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 mfunction 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 codelet 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 mbool 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 codeint 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 mdef 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 codearr = [1, 7]n = len(arr)m = 5print("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 mstatic 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 codepublic 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)
This article is contributed by Pratik Chhajer. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
