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\)
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
Editorial