# Check if any valid sequence is divisible by M

Given an array of N integers, using ‘+’ and ‘-‘ between the elements check if there is a way to form a sequence of numbers which evaluate to a number divisible by M

Examples:

```Input : arr = {1, 2, 3, 4, 6}
M = 4
Output : True,
There is a valid sequence i. e., (1 - 2
+ 3 + 4 + 6), which evaluates to 12 that
is divisible by 4

Input : arr = {1, 3, 9}
M = 2
Output : False
There is no sequence which evaluates to
a number divisible by M.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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:

 `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``; ` `} `

There are overlapping subproblems as shown in the image below (Note: the image represents the recursion tree till index = 3)

So, now we will solve this using dynamic programming

Method 1:
We apply Dynamic Programming with two states :-
(i) index,
(ii) 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.

## C++

 `// C++ program to check if any  ` `// valid sequence is divisible by M ` `#include ` `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; ` `} `

## Python3

 `# Python program to check if any  ` `# valid sequence is divisible by M ` ` `  `def` `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` `res ` ` `  `MAX` `=` `1000` `arr ``=` `[``1``, ``2``, ``3``, ``4``, ``6``]  ` `n ``=` `len``(arr)  ` `M ``=` `4` `dp ``=` `[[``-``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 `

Output:

```True
```

The Complexity of this method is O(N*sum) where sum is the maximum possible sum for the sequence of integers and N is the number of elements in the array.

Method 2(efficient):
This is more efficient than Method 1. Here also, we apply Dynamic Programming but with two different states :-
(i) index,
(ii) modulo
So DP[index][modulo] stores the modulus of the result of evaluation of the sequence formed till that index, with M.

## C++

 `#include ` `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  `

## Python 3

 `# Python3 Program to Check if any  ` `# valid sequence is divisible by M ` `MAX` `=` `100`  ` `  `def` `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``)] ``*` `MAX` ` `  `res ``=` `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 `

Output:

```True
```

The Complexity of this method is O(N*M).