Problem Statement: Balanced Sub-Arrays 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. Note: parity(x) denotes the remainder of dividing x by 2 A sub-array is the sequence of consecutive elements of the array. Constraint: 1<=N<=10^5

Intituiton: Observation 1: Characterizing the parity of the LCM The first step is to understand when the LCM of a subarray is odd or even. If all elements are odd, then their LCM is also odd. If the subarray contains at least one even element, then the LCM must be even. Therefore, parity(lcm(B)) = 1 if and only if every element of B is odd. Otherwise, parity(lcm(B)) = 0. This observation completely removes the need to compute the LCM. The problem now depends only on whether a subarray contains an even element. Observation 2: Splitting into Two Cases Using the previous observation, we can divide all subarrays into two categories. Case 1: The subarray contains at least one even element In this case, parity(lcm(B)) = 0 Hence, the subarray is balanced if and only if parity(sum(B)) = 0 In other words, we need to count subarrays with an "even sum". Case 2: Every element of the subarray is odd

In this case, parity(lcm(B)) = 1 Since every element is odd, the parity of the sum depends only on the parity of the number of elements. Therefore, parity(sum(B)) = parity(length(B)) So, among subarrays consisting entirely of odd numbers, only the "odd-length" subarrays satisfy the required condition. Thus, the original problem reduces to: Count all even-sum subarrays that contain at least one even element. Count all odd-length subarrays consisting entirely of odd numbers. Counting Even-Sum Subarrays:

From the previous section, we know that every subarray containing at least one even element must have an "even sum".

A subarray has an even sum if and only if the prefix sums at its two endpoints have the same parity. Let prefix[i] = (a1 + a2 + ... + ai) % 2 If two prefix sums have the same parity, then the subarray between them has an even sum. Therefore, while traversing the array, we maintain the frequency of prefix parities:

freq[0] = number of even prefix sums seen so far. freq[1] = number of odd prefix sums seen so far.

Initially, freq[0] = 1; freq[1] = 0; to account for the empty prefix. For every element:

Update the current prefix parity. Add "freq[currentParity]" to the answer, since every previous prefix with the same parity forms an even-sum subarray. Increment "freq[currentParity]".

This counts all subarrays having an even sum in O(N) time. code snippet: int evensumcnt=0; int freq[2]={0}; freq[0]=1; int sum=0; for(int i=0;i<n;i++){ sum+=vec[i]; int parity=sum%2; if(parity==1) evensumcnt+=freq[1]; else evensumcnt+=freq[0]; freq[parity]++; } Correcting the Overcount:

The previous step counts every even-sum subarray.

However, this also includes subarrays consisting entirely of odd numbers.

Such subarrays are not always balanced.

If every element of a subarray is odd, then

parity(lcm(B)) = 1

whereas an even-sum all-odd subarray has

parity(sum(B)) = 0

Hence, these subarrays were counted incorrectly and must be removed.

At the same time, all-odd subarrays having odd length are balanced because

every element is odd, parity(lcm(B)) = 1, and parity(sum(B)) = parity(length(B)) = 1.

Therefore, we need to

1. subtract all all-odd even-length subarrays,
2. add all all-odd odd-length subarrays. Counting All-Odd Subarrays Using RLE:

Notice that a subarray consisting entirely of odd numbers must lie completely inside a maximal consecutive block of odd elements.

Therefore, instead of examining every subarray individually, we process each maximal block of consecutive odd numbers independently.

Suppose the current block has length L.

The total number of subarrays inside this block is

total = L * (L + 1) / 2;

Now we need to count how many of these subarrays have odd length.

For a block of length L, the number of odd-length subarrays is oddLength = ((L + 1) / 2) * ((L + 2) / 2); This can be verified easily for small values of L:

L | Odd-length subarrays | -------------------- 1 | 1
| 2 | 2
| 3 | 4
| 4 | 6
| 5 | 9

The remaining subarrays have even length, so evenLength = total — oddLength; By processing every maximal odd block and accumulating these values, we obtain:

• the total number of all-odd odd-length subarrays, and
• the total number of all-odd even-length subarrays.

This entire step also runs in O(N) time. Proof (optional): Let f(L) denote the number of odd-length subarrays in a block of length L. One can derive f(L)=[L+1]/2 *[L+2]/2by counting valid starting positions for each odd length, or by induction. Final Answer: Let * evenSumCount = number of subarrays having an even sum (computed using prefix parity). * oddLengthCount = number of all-odd subarrays having odd length. * evenOddCount = number of all-odd subarrays having even length.

The required answer is answer = oddLengthCount+ (evenSumCount — evenOddCount);

This works because:

• evenSumCount counts every even-sum subarray.
• It incorrectly includes all-odd even-length subarrays, which are not balanced.
• Hence, we subtract evenOddCount.

• Finally, we add all-odd odd-length subarrays, which satisfy the required condition.

  Complexity Analysis

• Prefix parity traversal: O(N)

• Processing odd blocks using RLE: O(N)

Overall complexity:

Time Complexity: O(N) Auxiliary Space: O(1) here is my full solution:

include<bits/stdc++.h>

using namespace std; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; vectorvec(n,0); for(int i=0;i<n;i++) cin>>vec[i]; //finding total number of subarrays with even sum int evensumcnt=0; int freq[2]={0}; freq[0]=1; int sum=0; for(int i=0;i<n;i++){ sum+=vec[i]; int parity=sum%2; if(parity==1) evensumcnt+=freq[1]; else evensumcnt+=freq[0]; freq[parity]++; } // using rle to find the total number of subarrays with sum odd with all elements odd and counting even subarrays sum form with odd numbers int oddlencnt=0; int evenoddcnt=0; int len=0; for(int i=0;i<n;i++){ if(vec[i]%2==1){ len++; } else{ int a = (len+1)/2; int b= (len+2)/2; int totalen= (len*(len+1)/2); int oddcur=a*b; oddlencnt+=oddcur; evenoddcnt+=(totalen-oddcur); len=0; } } //to process last len if(len>0){ int a = (len+1)/2; int b= (len+2)/2; int totalen= (len*(len+1)/2); int oddcur=a*b; oddlencnt+=oddcur; evenoddcnt+=(totalen-oddcur); } int ans= oddlencnt+(evensumcnt-evenoddcnt); cout<<ans<<endl; }

}

Key Takeaway

The main challenge of this problem was not the implementation but identifying the right observations. Once we realize that the parity of the LCM depends only on whether the subarray contains an even element, the problem naturally decomposes into two independent counting problems: prefix parity for even-sum subarrays and RLE for all-odd subarrays.