Odd-Even Subarrays

★★★★★

4.2

126 votes

Algorithms, Dynamic Programming, Easy

Details

Problem

You are given an array A of N positive integer values. A subarray of this array is called Odd-Even subarray if the number of odd integers in this subarray is equal to the number of even integers in this subarray.

Find the number of Odd-Even subarrays for the given array.

Input Format:
The input consists of two lines.

First line denotes N - size of array.
Second line contains N space separated positive integers denoting the elements of array A.

Output Format:
Print a single integer, denoting the number of Odd-Even subarrays for the given array.

Constraints:

$1 \leq N \leq 2 \times 10^5$
$1 \leq A[i] \leq 10^9$

Sample Input

4
1 2 1 2

Sample Output

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

Let $A[i..j]$ denotes the subarray of A starting at index i and ending at index j.

The four subarrays in which number of odd integers are equal to number of even integers are:

$A[1..2] = [1, 2]$ contains one odd and one even integer

$A[2..3] = [2, 1]$ contains one odd and one even integer

$A[3..4] = [1, 2]$ contains one odd and one even integer

$A[1..4] = [1, 2, 1, 2]$ contains two odd and two even integers

Contributers:

Pranav Arora

Akash Sharma