Given a binary string of size N, you have to return the number of substrings that have even value in its decimal form.
Note: Most significant bit is on the right end side. For example - binary representation of 6 is 011. 
Example 1:
Input:
N = 3
S = "101"
Output: 2
Explanation : 
Substrings in S: 
1, 10, 101, 0, 01, 1
Corresponding decimal values:
1, 1, 5, 0, 2, 1
There are only 2 even decimal valued 
substrings.
Example 2:
Input:
N = 5
S = "10010"
Output: 
8
Explanation:
Substrings in S:
1, 0, 0, 1, 0, 10, 00, 01, 10, 100, 
001, 010, 1001, 0010 and 10010
Corresponding decimal Values are:
1, 0, 0, 1, 0, 1, 0, 2, 1, 1, 4, 2,
9, 4 ans 9
There are 8 decimal values which are even.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function evenDecimalSubStr() which takes the string S, its size N as input parameters and returns the number of substrings that has even value in its decimal form.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ T ≤ 1000
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Bit manipulation

Data structures

Starter code: #User function Template for python3
class Solution:
    def evenDecimalSubStr (self, N, S):
        # code here

Solutions:
class Solution:

	def evenDecimalSubStr(self, N, S):
		output = 0
		for i in range(N):
			if S[i] == '0':
				output += N - i
		return output


class Solution:

	def evenDecimalSubStr(self, N, S):
		ans = 0
		for i in range(N):
			if S[i] == '0':
				val = N - i
				if val != 0:
					ans += val
		return ans


from itertools import combinations

class Solution:

	def evenDecimalSubStr(self, N, S):
		count = 0
		for i in range(N):
			if S[i] == '0':
				count += N - i
		return count


class Solution:

	def evenDecimalSubStr(self, n, s):
		cnt = 0
		for i in range(0, n):
			if s[i] == '0':
				cnt += n - i
		return cnt
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		S = input()
		ob = Solution()
		print(ob.evenDecimalSubStr(N, S))


class Solution:

	def evenDecimalSubStr(self, N, S):
		res = 0
		for x in range(len(S)):
			if S[x] == '0':
				res += N - x
		return res


class Solution:

	def evenDecimalSubStr(self, n, S):
		count = 0
		for i in range(n):
			if S[i] == '0':
				count += n - i
		return count