Odd-Even Subarrays
Tag(s):

## Algorithms, Dynamic Programming, Easy, 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

Airtel Crack the Code

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs
• Algorithms > Graphs
• Algorithms > Greedy Algorithms
• Algorithms > String Algorithms
• Algorithms > Graphs