Given an array Arr[] of size N. Find the number of subarrays whose sum is an even number.
Example 1:
Input:
N = 6
Arr[] = {1, 2, 2, 3, 4, 1}
Output: 9
Explanation: The array {1, 2, 2, 3, 4, 1} 
has 9 such possible subarrays. These are-
 {1, 2, 2, 3}          Sum = 8
 {1, 2, 2, 3, 4}       Sum = 12
 {2}                   Sum = 2 (At index 1)
 {2, 2}                Sum = 4
 {2, 2, 3, 4, 1}       Sum = 12
 {2}                   Sum = 2 (At index 2)
 {2, 3, 4, 1}          Sum = 10
 {3, 4, 1}             Sum = 8
 {4}                   Sum = 4
Example 2:
Input:
N = 4
Arr[] = {1, 3, 1, 1}
Output: 4
Explanation: The array {1, 3, 1, 1} 
has 4 such possible subarrays.
These are-
 {1, 3}            Sum = 4
 {1, 3, 1, 1}      Sum = 6
 {3, 1}            Sum = 4
 {1, 1}            Sum = 2
Your Task:
You don't need to read input or print anything. Your task is to complete the function countEvenSum() which takes the array of integers arr[] and its size n as input parameters and returns an integer denoting the answer.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
1<= Arr[i] <=10^{9}

Difficulty: MEDIUM
Tags: Data structures

Mathematics
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def countEvenSum(self, arr, n):

        # code here

Solutions:
class Solution:

	def countEvenSum(self, arr, n):
		cnt = [0, 0]
		ans = 0
		for a in arr:
			if a % 2 == 0:
				ans += cnt[0] + 1
				cnt[0] += 1
			else:
				ans += cnt[1]
				(cnt[0], cnt[1]) = (cnt[1], cnt[0] + 1)
		return ans


class Solution:

	def countEvenSum(self, arr, n):
		even = 0
		odd = 0
		sum1 = 0
		for i in range(n):
			sum1 += arr[i]
			if sum1 % 2 == 0:
				even += 1
			else:
				odd += 1
		count1 = odd * (odd - 1) // 2 + even * (even - 1) // 2 + even
		return count1


class Solution:

	def countEvenSum(self, a, n):
		s = 0
		ecnt = 0
		ocnt = 0
		ans = 0
		for i in range(n):
			s += a[i]
			if s % 2 == 0:
				ans += ecnt + 1
				ecnt += 1
			else:
				ans += ocnt
				ocnt += 1
		return ans


class Solution:

	def countEvenSum(self, arr, n):
		c = 0
		f = [0, 0]
		s = 0
		for i in range(n):
			s += arr[i]
			if s % 2 == 0:
				c += f[0] + 1
				f[0] += 1
			else:
				c += f[1]
				f[1] += 1
		return c


def countSpecial(n, arr):
	(e, o) = (0, 0)
	if arr[0] % 2 == 1:
		o += 1
	else:
		e += 1
	for i in range(1, n):
		arr[i] = arr[i - 1] + arr[i]
		if arr[i] % 2 == 1:
			o += 1
		else:
			e += 1
	result = e * (e + 1) // 2
	result += o * (o + 1) // 2 - o
	return result

class Solution:

	def countEvenSum(self, arr, n):
		return countSpecial(n, arr)


class Solution:

	def countEvenSum(self, arr, n):
		(even, odd) = (0, 0)
		s = 0
		ans = 0
		for i in arr:
			s += i
			if s % 2 == 0:
				even += 1
			else:
				odd += 1
		ans = even * (even - 1) // 2 + odd * (odd - 1) // 2 + even
		return ans


class Solution:

	def countEvenSum(self, arr, n):
		odd = 0
		even = 0
		summa = 0
		for item in arr:
			summa += item
			odd += summa % 2
			even += summa % 2 == 0
		count = even
		summa = 0
		for item in arr:
			summa += item
			if summa % 2:
				odd -= 1
				count += odd
			else:
				even -= 1
				count += even
		return count


from collections import defaultdict as dd

class Solution:

	def countEvenSum(self, arr, n):
		(ans, cnt, sm) = (0, dd(int), 0)
		for el in arr:
			sm += el
			x = sm & 1
			if x == 0:
				ans += 1
			ans += cnt[x]
			cnt[x] += 1
		return ans


class Solution:

	def countEvenSum(self, arr, n):
		temp = [1, 0]
		result = 0
		sum = 0
		for i in range(n):
			sum = ((sum + arr[i]) % 2 + 2) % 2
			temp[sum] += 1
		result = result + temp[0] * (temp[0] - 1) // 2
		result = result + temp[1] * (temp[1] - 1) // 2
		return result


class Solution:

	def countEvenSum(self, arr, n):
		(o, e, c) = (0, 0, 0)
		for i in range(n):
			if arr[i] % 2 == 0:
				o = o
				e += 1
			else:
				t = e
				e = o
				o = t + 1
			c += e
		return c


class Solution:

	def countEvenSum(self, arr, n):
		eve = odd = s = out = 0
		for i in range(n):
			s += arr[i]
			if s % 2 == 0:
				out += 1 + eve
				eve += 1
			else:
				out += odd
				odd += 1
		return out


class Solution:

	def countEvenSum(self, arr, n):
		odd = 0
		even = 0
		count = 0
		for i in range(n):
			if arr[i] % 2 == 0:
				odd = odd
				even += 1
			else:
				temp = even
				even = odd
				odd = temp + 1
			count = count + even
		return count


class Solution:

	def countEvenSum(self, arr, n):
		sum = 0
		t = 0
		for i in reversed(range(n)):
			if arr[i] % 2 == 1:
				t = n - i - 1 - t
			else:
				t = t + 1
			sum = sum + t
		return sum
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.countEvenSum(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def countEvenSum(self, arr, n):
		e = 0
		o = 0
		s = 0
		ans = 0
		for i in range(n):
			s += arr[i]
			if s % 2 == 0:
				ans += 1 + e
				e += 1
			else:
				ans += o
				o += 1
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.countEvenSum(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def countEvenSum(self, arr, n):
		currsum = 0
		hm = {}
		count = 0
		for i in range(n):
			currsum += arr[i]
			if currsum % 2 == 0:
				count += 1
				if hm.get(2):
					count += hm[2]
					hm[2] += 1
				else:
					hm[2] = 1
			elif hm.get(1):
				count += hm[1]
				hm[1] += 1
			else:
				hm[1] = 1
		return count
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.countEvenSum(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def countEvenSum(self, arr, n):
		sum = 0
		t = 0
		for i in reversed(range(n)):
			if arr[i] % 2 == 1:
				t = n - i - 1 - t
			else:
				t = t + 1
			sum = sum + t
		return sum


class Solution:

	def countEvenSum(self, arr, n):
		s = 0
		res = 0
		for i in range(n - 1, -1, -1):
			if arr[i] & 1:
				s = n - i - 1 - s
			else:
				s = s + 1
			res = res + s
		return res


class Solution:

	def countEvenSum(self, arr, n):
		even = 0
		odd = 0
		sume = 0
		ans = 0
		for a in arr:
			sume += a
			if sume % 2 == 0:
				ans += 1 + even
				even += 1
			else:
				ans += odd
				odd += 1
		return ans


class Solution:

	def countEvenSum(self, arr, n):
		sub_parity = [0, 0]
		total_even = 0
		odd = 0
		even = 0
		for i in range(n):
			if arr[i] & 1:
				odd = sub_parity[0] + 1
				even = sub_parity[1]
			else:
				odd = sub_parity[1]
				even = sub_parity[0] + 1
			sub_parity = [even, odd]
			total_even += even
		return total_even


class Solution:

	def countEvenSum(self, arr, n):
		odd = 0
		even = 0
		cnt = 0
		for i in range(len(arr)):
			if arr[i] % 2 == 0:
				even = even + 1
			else:
				tmp = even
				even = odd
				odd = tmp + 1
			cnt += even
		return cnt


class Solution:

	def countEvenSum(self, arr, n):
		csm = odd = ev = 0
		for i in arr:
			csm += i
			if csm & 1:
				odd += 1
			else:
				ev += 1
		ans = n * (n + 1) // 2 - odd * (1 + ev)
		return ans


class Solution:

	def countEvenSum(self, arr, n):
		(ce, co) = (0, 0)
		s = 0
		for x in arr:
			if x % 2 == 0:
				ce += 1
			else:
				old_co = co
				co = ce + 1
				ce = old_co
			s += ce
		return s


class Solution:

	def countEvenSum(self, arr, n):
		even = 0
		odd = 0
		sum = 0
		r = 0
		for i in range(n):
			sum += arr[i]
			if sum % 2 != 0:
				r += odd
				odd = odd + 1
			else:
				r += even + 1
				even = even + 1
		return r


class Solution:

	def countEvenSum(self, arr, n):
		sm = 0
		(ev, od) = (0, 0)
		for i in range(n):
			sm += arr[i]
			if sm % 2 == 0:
				ev += 1
			else:
				od += 1
		return ev * (ev + 1) // 2 + od * (od - 1) // 2


class Solution:

	def countEvenSum(self, arr, n):
		ans = 0
		sm = 0
		(eve, odd) = (0, 0)
		for i in range(n):
			sm += arr[i]
			if sm % 2 != 0:
				ans += odd
				odd += 1
			else:
				ans += eve + 1
				eve += 1
		return ans