All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Odd-Even Subarrays
/

Algorithms, Dynamic Programming, Introduction to Dynamic Programming 1

Problem
Editorial
Analytics

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
4
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

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?