Given an array of N integers, using ‘+’ and ‘-‘ between the elements check if there is a way to form a sequence of numbers that evaluate to a number divisible by M
Examples:
Input: arr = {1, 2, 3, 4, 6}
M = 4
Output: True
Explanation:
There is a valid sequence i.e., (1 – 2
+ 3 + 4 + 6), which evaluates to 12 that
is divisible by 4Input: arr = {1, 3, 9}
M = 2
Output: False
Explanation:
There is no sequence which evaluates to
a number divisible by M.
A simple solution is to recursively consider all possible scenarios ie either use a ;+’ or a ‘-‘ operator between the elements and maintain a variable sum which stores the result.If this result is divisible by M then return true else return false.
Recursive implementation is as follows:
C++
bool isPossible(int index, int sum){ // Base case if (index == n) { // check if sum is divisible by M if ((sum % M) == 0) return true; return false; } // recursively call by considering '+' // or '-' between index and index+1 // 1.Try placing '+' bool placeAdd = isPossible(index + 1, sum + arr[index]); // 2. Try placing '-' bool placeMinus = isPossible(index + 1, sum - arr[index]); if (placeAdd || placeMinus) return true; return false;} |
Java
static boolean isPossible(int index, int sum){ // Base case if (index == n) { // Check if sum is divisible by M if ((sum % M) == 0) return true; return false; } // Recursively call by considering '+' // or '-' between index and index+1 // 1.Try placing '+' boolean placeAdd = isPossible(index + 1, sum + arr[index]); // 2. Try placing '-' boolean placeMinus = isPossible(index + 1, sum - arr[index]); if (placeAdd || placeMinus) return true; return false;}// This code is contributed by rutvik_56. |
Python3
def isPossible(index, sum): # Base case if (index == n): # check if sum is divisible by M if ((sum % M) == 0): return True; return False; # recursively call by considering '+' # or '-' between index and index+1 # 1.Try placing '+' placeAdd = isPossible(index + 1, sum + arr[index]); # 2. Try placing '-' placeMinus = isPossible(index + 1, sum - arr[index]); if (placeAdd or placeMinus): return True; return False;# This code is contributed by pratham76. |
C#
static bool isPossible(int index, int sum){ // Base case if (index == n) { // Check if sum is divisible by M if ((sum % M) == 0) return true; return false; } // Recursively call by considering '+' // or '-' between index and index+1 // 1.Try placing '+' bool placeAdd = isPossible(index + 1, sum + arr[index]); // 2. Try placing '-' bool placeMinus = isPossible(index + 1, sum - arr[index]); if (placeAdd || placeMinus) return true; return false;}// This code is contributed by divyesh072019 |
Javascript
<script>function isPossible(index , sum){ // Base case if (index == n) { // Check if sum is divisible by M if ((sum % M) == 0) return true; return false; } // Recursively call by considering '+' // or '-' between index and index+1 // 1.Try placing '+' let placeAdd = isPossible(index + 1, sum + arr[index]); // 2. Try placing '-' let placeMinus = isPossible(index + 1, sum - arr[index]); if (placeAdd || placeMinus) return true; return false;}// This code is contributed by Amit Katiyar </script> |
There are overlapping subproblems as shown in the image below (Note: the image represents the recursion tree till index = 3)
Better Approach: To optimize the above approach use dynamic programming.
Method 1: We apply Dynamic Programming with two states :-
- index,
- sum
So DP[index][sum] stores the current index we are at and sum stores the result of evaluation of the sequence formed till that index.
Below is the implementation of the above approach:
C++
// C++ program to check if any // valid sequence is divisible by M#include <bits/stdc++.h>using namespace std;const int MAX = 1000;bool isPossible(int n, int index, int sum, int M, int arr[], int dp[][MAX]){ // Base case if (index == n) { // check if sum is divisible by M if ((sum % M) == 0) return true; return false; } // check if the current state // is already computed if (dp[index][sum] != -1) return dp[index][sum]; // 1.Try placing '+' bool placeAdd = isPossible(n, index + 1, sum + arr[index], M, arr, dp); // 2. Try placing '-' bool placeMinus = isPossible(n, index + 1, sum - arr[index], M, arr, dp); // calculate value of res for recursive case bool res = (placeAdd || placeMinus); // store the value for res for current // states and return for parent call dp[index][sum] = res; return res;}int main(){ int arr[] = { 1, 2, 3, 4, 6 }; int n = sizeof(arr)/sizeof(arr[0]); int M = 4; int dp[n + 1][MAX]; memset(dp, -1, sizeof(dp)); bool res; res = isPossible(n, 0, 0, M, arr, dp); cout << (res ? "True" : "False") << endl; return 0;} |
Java
// Java program to check if any // valid sequence is divisible by Mimport java.util.*;class GFG { static final int MAX = 1000; static boolean isPossible(int n, int index, int sum, int M, int arr[], int dp[][]) { // Base case if (index == n) { // check if sum is divisible by M if ((sum % M) == 0) return true; return false; } else if(sum < 0 || sum >= MAX) return false; // check if the current state // is already computed if (dp[index][sum] != -1) { if(dp[index][sum] == 0) return false; return true; } // 1.Try placing '+' boolean placeAdd = isPossible(n, index + 1, sum + arr[index], M, arr, dp); // 2. Try placing '-' boolean placeMinus = isPossible(n, index + 1, sum - arr[index], M, arr, dp); // calculate value of res for recursive case boolean res = (placeAdd || placeMinus); // store the value for res for current // states and return for parent call dp[index][sum] = (res) ? 1 : 0; return res; } // Driver code public static void main(String args[]) { int arr[] = { 1, 2, 3, 4, 6 }; int n = arr.length; int M = 4; int dp[][] = new int[n + 1][MAX]; for(int i = 0; i < n + 1; i++) Arrays.fill(dp[i], -1); boolean res; res = isPossible(n, 0, 0, M, arr, dp); System.out.println((res ? "True" : "False")); }}// This code is contributed by ghanshyampandey |
Python3
# Python3 program to check if any # valid sequence is divisible by Mdef isPossible(n, index, Sum, M, arr, dp): global MAX # Base case if index == n: # check if sum is divisible by M if (Sum % M) == 0: return True return False # check if the current state # is already computed if dp[index][Sum] != -1: return dp[index][Sum] # 1.Try placing '+' placeAdd = isPossible(n, index + 1, Sum + arr[index], M, arr, dp) # 2. Try placing '-' placeMinus = isPossible(n, index + 1, Sum - arr[index], M, arr, dp) # calculate value of res for recursive case res = placeAdd or placeMinus # store the value for res for current # states and return for parent call dp[index][Sum] = res return resMAX = 1000arr = [1, 2, 3, 4, 6] n = len(arr) M = 4dp = [[-1]*MAX for i in range(n+1)]res = isPossible(n, 0, 0, M, arr, dp) if res: print(True)else: print(False) # this code is contributed by PranchalK |
C#
// C# program to check if any // valid sequence is divisible by Musing System; class GFG { static int MAX = 1000; static Boolean isPossible(int n, int index, int sum, int M, int []arr, int [,]dp) { // Base case if (index == n) { // check if sum is divisible by M if ((sum % M) == 0) return true; return false; } else if(sum < 0 || sum >= MAX) return false; // check if the current state // is already computed if (dp[index,sum] != -1) { if(dp[index,sum] == 0) return false; return true; } // 1.Try placing '+' Boolean placeAdd = isPossible(n, index + 1, sum + arr[index], M, arr, dp); // 2. Try placing '-' Boolean placeMinus = isPossible(n, index + 1, sum - arr[index], M, arr, dp); // calculate value of res for recursive case Boolean res = (placeAdd || placeMinus); // store the value for res for current // states and return for parent call dp[index,sum] = (res) ? 1 : 0; return res; } // Driver code public static void Main(String []args) { int []arr = { 1, 2, 3, 4, 6 }; int n = arr.Length; int M = 4; int [,]dp = new int[n + 1, MAX]; for(int i = 0; i < n + 1; i++) for(int j = 0; j < MAX; j++) dp[i, j] = -1; Boolean res; res = isPossible(n, 0, 0, M, arr, dp); Console.WriteLine((res ? "True" : "False")); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// javascript program to check if any // valid sequence is divisible by Mvar MAX = 1000; function isPossible(n , index , sum,M , arr , dp){ // Base case if (index == n) { // check if sum is divisible by M if ((sum % M) == 0) return true; return false; } else if(sum < 0 || sum >= MAX) return false; // check if the current state // is already computed if (dp[index][sum] != -1) { if(dp[index][sum] == 0) return false; return true; } // 1.Try placing '+' var placeAdd = isPossible(n, index + 1, sum + arr[index], M, arr, dp); // 2. Try placing '-' var placeMinus = isPossible(n, index + 1, sum - arr[index], M, arr, dp); // calculate value of res for recursive case var res = (placeAdd || placeMinus); // store the value for res for current // states and return for parent call dp[index][sum] = (res) ? 1 : 0; return res;}// Driver codevar arr = [ 1, 2, 3, 4, 6 ];var n = arr.length;var M = 4;var dp = Array(n+1).fill(-1).map(x => Array(MAX).fill(-1));res = isPossible(n, 0, 0, M, arr, dp);document.write((res ? "True" : "False"));// This code contributed by shikhasingrajput </script> |
Output:
True
Time Complexity: O(N*sum), where the sum is the maximum possible sum for the sequence of integers and N is the number of elements in the array.
Auxiliary Space: O(N * MAX), here MAX = 1000
Method 2(efficient): This is more efficient than Method 1. Here also, we apply Dynamic Programming but with two different states:
- index,
- modulo
So DP[index][modulo] stores the modulus of the result of the evaluation of the sequence formed till that index, with M.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;const int MAX = 100;int isPossible(int n, int index, int modulo, int M, int arr[], int dp[][MAX]){ // Calculate modulo for this call modulo = ((modulo % M) + M) % M; // Base case if (index == n) { // check if sum is divisible by M if (modulo == 0) return 1; return 0; } // check if the current state is // already computed if (dp[index][modulo] != -1) return dp[index][modulo]; // 1.Try placing '+' int placeAdd = isPossible(n, index + 1, modulo + arr[index], M, arr, dp); // 2. Try placing '-' int placeMinus = isPossible(n, index + 1, modulo - arr[index], M, arr, dp); // calculate value of res for recursive // case bool res = (placeAdd || placeMinus); // store the value for res for current // states and return for parent call dp[index][modulo] = res; return res;}int main(){ int arr[] = { 1, 2, 3, 4, 6 }; int n = sizeof(arr)/sizeof(arr[0]); int M = 4; // MAX is the Maximum value M can take int dp[n + 1][MAX]; memset(dp, -1, sizeof(dp)); bool res; res = isPossible(n, 1, arr[0], M, arr, dp); cout << (res ? "True" : "False") << endl; return 0;} |
Java
// Java implementation of above approach class GFG { static int MAX = 100; static int isPossible(int n, int index, int modulo, int M, int arr[], int dp[][]) { // Calculate modulo for this call modulo = ((modulo % M) + M) % M; // Base case if (index == n) { // check if sum is divisible by M if (modulo == 0) { return 1; } return 0; } // check if the current state is // already computed if (dp[index][modulo] != -1) { return dp[index][modulo]; } // 1.Try placing '+' int placeAdd = isPossible(n, index + 1, modulo + arr[index], M, arr, dp); // 2. Try placing '-' int placeMinus = isPossible(n, index + 1, modulo - arr[index], M, arr, dp); // calculate value of res for // recursive case int res = placeAdd; // store the value for res for current // states and return for parent call dp[index][modulo] = res; return res; } // Driver code public static void main(String[] args) { int arr[] = {1, 2, 3, 4, 6}; int n = arr.length; int M = 4; // MAX is the Maximum value M can take int dp[][] = new int[n + 1][MAX]; for (int i = 0; i < n + 1; i++) { for (int j = 0; j < MAX; j++) { dp[i][j] = -1; } } boolean res; if (isPossible(n, 1, arr[0], M, arr, dp) == 1) { res = true; } else { res = false; } System.out.println(res ? "True" : "False"); }}// This code is contributed by // PrinciRaj1992 |
Python3
# Python3 Program to Check if any # valid sequence is divisible by MMAX = 100def isPossible(n, index, modulo, M, arr, dp): # Calculate modulo for this call modulo = ((modulo % M) + M) % M # Base case if (index == n): # check if sum is divisible by M if (modulo == 0): return 1 return 0 # check if the current state is # already computed if (dp[index][modulo] != -1): return dp[index][modulo] # 1.Try placing '+' placeAdd = isPossible(n, index + 1, modulo + arr[index], M, arr, dp) # 2. Try placing '-' placeMinus = isPossible(n, index + 1, modulo - arr[index], M, arr, dp) # calculate value of res # for recursive case res = bool(placeAdd or placeMinus) # store the value for res for current # states and return for parent call dp[index][modulo] = res return res # Driver code arr = [ 1, 2, 3, 4, 6 ] n = len(arr)M = 4# MAX is the Maximum value # M can take dp = [[-1] * (n + 1)] * MAXres = isPossible(n, 1, arr[0], M, arr, dp) if(res == True): print("True") else: print("False")# This code is contributed by ash264 |
C#
// C# implementation of above approach using System; class GFG { static int MAX = 100; static int isPossible(int n, int index, int modulo, int M, int []arr, int [,]dp) { // Calculate modulo for this call modulo = ((modulo % M) + M) % M; // Base case if (index == n) { // check if sum is divisible by M if (modulo == 0) { return 1; } return 0; } // check if the current state is // already computed if (dp[index, modulo] != -1) { return dp[index, modulo]; } // 1.Try placing '+' int placeAdd = isPossible(n, index + 1, modulo + arr[index], M, arr, dp); // 2. Try placing '-' int placeMinus = isPossible(n, index + 1, modulo - arr[index], M, arr, dp); // calculate value of res for // recursive case int res = placeAdd; // store the value for res for current // states and return for parent call dp[index, modulo] = res; return res; } // Driver code public static void Main() { int []arr = {1, 2, 3, 4, 6}; int n = arr.Length; int M = 4; // MAX is the Maximum value M can take int [,]dp = new int[n + 1,MAX]; for (int i = 0; i < n + 1; i++) { for (int j = 0; j < MAX; j++) { dp[i, j] = -1; } } bool res; if (isPossible(n, 1, arr[0], M, arr, dp) == 1) { res = true; } else { res = false; } Console.WriteLine(res ? "True" : "False"); }}//This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of above approach const MAX = 100;function isPossible(n, index, modulo, M, arr, dp){ // Calculate modulo for this call modulo = ((modulo % M) + M) % M; // Base case if (index == n) { // Check if sum is divisible by M if (modulo == 0) { return 1; } return 0; } // check if the current state is // already computed if (dp[index][modulo] != -1) { return dp[index][modulo]; } // 1.Try placing '+' var placeAdd = isPossible(n, index + 1, modulo + arr[index], M, arr, dp); // 2. Try placing '-' var placeMinus = isPossible(n, index + 1, modulo - arr[index], M, arr, dp); // Calculate value of res for // recursive case var res = placeAdd; // Store the value for res for current // states and return for parent call dp[index][modulo] = res; return res;}// Driver codevar arr = [ 1, 2, 3, 4, 6 ];var n = arr.length;var M = 4;// MAX is the Maximum value M can takevar dp = Array(n + 1);for(i = 0; i < n + 1; i++){ dp[i] = Array(MAX).fill(-1);}var res;if (isPossible(n, 1, arr[0], M, arr, dp) == 1){ res = true;} else{ res = false;}document.write(res ? "True" : "False");// This code is contributed by gauravrajput1 </script> |
Output
True
Time Complexity: O(N*M).
Auxiliary Space: O(N * MAX), here MAX = 100
Efficient Approach: Follow the steps below in order to solve the problem:
- Evaluate Modulo of all the array element with respect to the given number and store it in the new array, lets say ModArray[].
- Evaluate the sum of the ModArray and store it in sum and check if the sum%M==0 then the output is “true” and return.
- If the sum is odd there will be no case that the following can evaluate to be the number which is divisible by M. Print “False” and return.
- Check if the sum is even then divided it by 2 this is because we have previously summed them and now the task is to delete it so it’s needed to delete it twice hence the number should be even.
- Remove the first element from the ModArray since it is not possible to place minus on the first element.
- Now the solution is converted into the problem where we want to evaluate that whether there exists a solution so that the sum of the elements of a ModArray is equal to the sum or not.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if any valid// sequence is divisible by Mvoid func(int n, int m, int A[]){ // DEclare mod array vector<int> ModArray(n); int sum = 0; // Calculate the mod array for (int i = 0; i < n; i++) { ModArray[i] = A[i] % m; sum += ModArray[i]; } sum = sum % m; // Check if sum is divisible by M if (sum % m == 0) { cout << "True"; return; } // Check if sum is not divisible by 2 if (sum % 2 != 0) { cout << "False"; } else { // Remove the first element from // the ModArray since it is not // possible to place minus // on the first element ModArray.erase(ModArray.begin()); int i = 0; // Decrease the size of array int j = ModArray.size() - 1; // Sort the array sort(ModArray.begin(), ModArray.end()); sum = sum / 2; int i1, i2; // Loop until the pointer // cross each other while (i <= j) { int s = ModArray[i] + ModArray[j]; // Check if sum becomes equal if (s == sum) { i1 = i; i2 = j; cout << "True"; break; } // Increase and decrease // the pointer accordingly else if (s > sum) j--; else i++; } }}// Driver codeint main(){ int m = 2; int a[] = { 1, 3, 9 }; int n = sizeof a / sizeof a[0]; // Function call func(n, m, a);} |
Java
// Java program for the above approachimport java.util.*; class GFG{ // Function to check if any valid// sequence is divisible by Mstatic void func(int n, int m, int []A){ // Declare mod array Vector<Integer> ModArray = new Vector<>(); for(int i = 0; i < n; i++) ModArray.add(0); int sum = 0; // Calculate the mod array for(int i = 0; i < n; i++) { ModArray.set(i, A[i] % m); sum += ((int)ModArray.get(i)); } sum = sum % m; // Check if sum is divisible by M if (sum % m == 0) { System.out.println("True"); return; } // Check if sum is not divisible by 2 if (sum % 2 != 0) { System.out.println("False"); } else { // Remove the first element from // the ModArray since it is not // possible to place minus // on the first element ModArray.remove(0); int i = 0; // Decrease the size of array int j = ModArray.size() - 1; // Sort the array Collections.sort(ModArray); sum = sum / 2; int i1, i2; // Loop until the pointer // cross each other while (i <= j) { int s = (int)ModArray.get(i) + (int)ModArray.get(j); // Check if sum becomes equal if (s == sum) { i1 = i; i2 = j; System.out.println("True"); break; } // Increase and decrease // the pointer accordingly else if (s > sum) j--; else i++; } }}// Driver codepublic static void main(String args[]) { int m = 2; int []a = { 1, 3, 9 }; int n = a.length; // Function call func(n, m, a);}}// This code is contributed by Stream_Cipher |
Python3
# Python3 program for the above approach# Function to check if any valid# sequence is divisible by Mdef func(n, m, A): # DEclare mod array ModArray = [0]*n Sum = 0 # Calculate the mod array for i in range(n): ModArray[i] = A[i] % m Sum += ModArray[i] Sum = Sum % m # Check if sum is divisible by M if (Sum % m == 0) : print("True") return # Check if sum is not divisible by 2 if (Sum % 2 != 0) : print("False") else : # Remove the first element from # the ModArray since it is not # possible to place minus # on the first element ModArray.pop(0) i = 0 # Decrease the size of array j = len(ModArray) - 1 # Sort the array ModArray.sort() Sum = Sum // 2 # Loop until the pointer # cross each other while (i <= j) : s = ModArray[i] + ModArray[j] # Check if sum becomes equal if (s == Sum) : i1 = i i2 = j print("True") break # Increase and decrease # the pointer accordingly elif (s > Sum): j -= 1 else: i += 1# Driver code m = 2a = [ 1, 3, 9 ]n = len(a)# Function callfunc(n, m, a)# This code is contributed by divyeshrabadiya07 |
C#
// C# program for the above approachusing System.Collections.Generic; using System; class GFG{ // Function to check if any valid// sequence is divisible by Mstatic void func(int n, int m, int []A){ // Declare mod array List<int> ModArray = new List<int>(); for(int i = 0; i < n; i++) ModArray.Add(0); int sum = 0; // Calculate the mod array for(int i = 0; i < n; i++) { ModArray[i] = (A[i] % m); sum += ((int)ModArray[i]); } sum = sum % m; // Check if sum is divisible by M if (sum % m == 0) { Console.WriteLine("True"); return; } // Check if sum is not divisible by 2 if (sum % 2 != 0) { Console.WriteLine("False"); } else { // Remove the first element from // the ModArray since it is not // possible to place minus // on the first element ModArray.Remove(0); int i = 0; // Decrease the size of array int j = ModArray.Count - 1; // Sort the array ModArray.Sort(); sum = sum / 2; int i1, i2; // Loop until the pointer // cross each other while (i <= j) { int s = (int)ModArray[i] + (int)ModArray[j]; // Check if sum becomes equal if (s == sum) { i1 = i; i2 = j; Console.WriteLine("True"); break; } // Increase and decrease // the pointer accordingly else if (s > sum) j--; else i++; } }}// Driver codepublic static void Main() { int m = 2; int []a = { 1, 3, 9 }; int n = a.Length; // Function call func(n, m, a);}}// This code is contributed by Stream_Cipher |
Javascript
<script> // Javascript program for the above approach // Function to check if any valid // sequence is divisible by M function func(n, m, A) { // Declare mod array let ModArray = []; for(let i = 0; i < n; i++) ModArray.push(0); let sum = 0; // Calculate the mod array for(let i = 0; i < n; i++) { ModArray[i] = A[i] % m; sum += ModArray[i]; } sum = sum % m; // Check if sum is divisible by M if (sum % m == 0) { document.write("True"); return; } // Check if sum is not divisible by 2 if (sum % 2 != 0) { document.write("False"); } else { // Remove the first element from // the ModArray since it is not // possible to place minus // on the first element ModArray.shift(); let i = 0; // Decrease the size of array let j = ModArray.length - 1; // Sort the array ModArray.sort(function(a, b){return a - b}); sum = parseInt(sum / 2, 10); let i1, i2; // Loop until the pointer // cross each other while (i <= j) { let s = ModArray[i] + ModArray[j]; // Check if sum becomes equal if (s == sum) { i1 = i; i2 = j; document.write("True"); break; } // Increase and decrease // the pointer accordingly else if (s > sum) j--; else i++; } } } let m = 2; let a = [ 1, 3, 9 ]; let n = a.length; // Function call func(n, m, a); </script> |
Output
False
Time Complexity: O(n * log n)
Auxiliary Space: O(n)
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!
