All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

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...
Your Rating:

Contributor

This Problem was Asked in

Airtel

Challenge Name

Airtel Crack the Code

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?