Balanced Sub-Arrays

3.4

5 votes
Introduction to Dynamic Programming 1, Number theory, Arrays, Algorithms, Dynamic Programming
Problem

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 A1,A2,,AN​.

Output Format:

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

 Constraints:

  • 1T200
  • 1N105
  • 1Ai105 for each valid i
  • The sum of N over all test cases does not exceed 106
Time Limit: 1.5
Memory Limit: 256
Source Limit:
Explanation
  • Test case 1: The balanced sub-arrays are [1],[1,2,3],[2] and [3].
  • Test case 2The balanced sub-arrays are [2],[9],[6],[6,4] and [4].
Editor Image

?