Given an array of N integers, using ‘+’ and ‘-‘ between the elements check if there is a way to form a sequence of numbers that evaluates a number divisible by M.
 
Example 1:
Ã¢â¬â¹Input : arr[ ] = {1, 2, 3, 4, 6} and M = 4
Output : 1
Explanation:
There is a valid sequence i. e., 
(1 - 2 + 3 + 4 + 6), which evaluates to 12 
that is divisible by 4.
Example 2:
Input : arr[ ] = {1, 3, 9} 
Output :  0 
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function validSequence() that takes an array (arr), sizeOfArray (n), an integer M and return the true if there is a way to form a sequence of numbers which evaluate to a number divisible by M else return false. The driver code takes care of the printing.
Expected Time Complexity: O(N*M).
Expected Auxiliary Space: O(N*M).
 
Constraints:
1 ≤ N < 1000
1 ≤ M <1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Dynamic programming

Data structures

Mathematics

Starter code: #User function Template for python3



def validSequence (arr, n, m) : 

    #Complete the function

    



Solutions:
def validSequence(arr, n, m):
	dp = []
	for i in range(n + 1):
		dp.append([-1] * m)

	def recur(i, arr, n, m, su):
		if i == n:
			if su == 0:
				return True
			else:
				return False
		if dp[i][su] != -1:
			return dp[i][su]
		val1 = recur(i + 1, arr, n, m, (su + arr[i]) % m)
		val2 = recur(i + 1, arr, n, m, (su - arr[i]) % m)
		dp[i][su] = val1 or val2
		return dp[i][su]
	return recur(0, arr, n, m, 0)


def validSequence(arr, n, m):
	set1 = set([0])
	for item in arr:
		set2 = set()
		for num in set1:
			set2.add((num - item) % m)
			set2.add((num + item) % m)
		set1 = set2.copy()
	return 0 in set1


def validSequence(arr, n, m):
	if n == 1:
		return arr[0] % m == 0

	def solve(idx, rem, d={}):
		if (idx, rem) in d:
			return d[idx, rem]
		if idx == n and rem == 0:
			return True
		if idx == n:
			return False
		first = (rem + arr[idx]) % m
		second = (rem - arr[idx]) % m
		d[idx, rem] = solve(idx + 1, first, d) or solve(idx + 1, second, d)
		return d[idx, rem]
	return solve(1, arr[0])


def validSequence(arr, n, m):
	dp = dict()

	def helper(i, vsf, dp):
		if i == n and vsf % m == 0:
			return True
		if i >= n:
			return False
		form = 'i:' + str(i) + ' ' + 'vsf:' + str(vsf)
		if form in dp:
			return dp[form]
		add = helper(i + 1, (vsf + arr[i]) % m, dp)
		sub = helper(i + 1, (vsf - arr[i]) % m, dp)
		dp[form] = add or sub
		return dp[form]
	return helper(1, arr[0], dp)