Balanced Sub-Arrays
Practice
3.4 (5 votes)
Introduction to dynamic programming 1
Number theory
Arrays
Algorithms
Dynamic programming
Problem
59% Success 585 Attempts 30 Points 1.5s Time Limit 256MB Memory 1024 KB Max Code

An array \(B\) is called balanced if \(parity(sum(B)) = parity(lcm(B))\). Given an array \(A\) of size \(N\), find the count of balanced sub-arrays of \(A\).

As of friendly reminder,

  •  \(parity(x)\) denotes the remainder of dividing \(x\) by \(2\)
  • A sub-array is the sequence of consecutive elements of the array.

 Input Format:

  • The first line of the input contains a single integer \(T\) - the number of test cases. The description of \(T\) test cases follows.
  • The first line of each test case contains a single integer \(N\).
  • The second line contains \(N\) space-separated integers \(A_1, A_2, \ldots, A_N\)​.

Output Format:

  • For each test case print a single integer — the answer to the problem.

 Constraints:

  • \(1 \leq T \leq 200\)
  • \(1 \leq N \leq 10^{5}\)
  • \(1 \leq A_i \leq 10^{5}\) for each valid \(i\)
  • The sum of \(N\) over all test cases does not exceed \(10^6\)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
11 votes
Tags:
AlgorithmsApprovedCompletedMediumOpen
Points:30
39 votes
Tags:
ApprovedBit ManipulationData StructuresDynamic ProgrammingMediumOpenSegment Trees
Points:30
866 votes
Tags:
Medium