How to find the count of subarrays in an array whose sum is odd in O(N) time complexity ?

Question

Constraints :

1<=N<=1000000

1<=A[i]<=1000000000

Example :

4 5 6 8  

Output : 4 { {4},{6}.{6,8},{8} } are all subarrays with even sum in the array  .  

Note :

1)Algorithm-explanation is must .

2)Adding code is optional .

Answer 1

1. maintain a running sum, we need to find whether its sum is odd or even, we only care of its first bit to check for even / odd
2. at every stage no of possible subarray increases by n example {6,5,4,9} then the total number of the possible subarray is 1+2+3+4 = 10,
3. in order to count all the possible subarray with even sum, we need to see how many times we have seen that parity (even / odd) and add it to the answer.
4. int the end we can get the required number of subarray with odd, even sum
5. for an odd sum just find the total number of subarray with even sum and subtract this value with total number of subarray possible.

================================================

DRY RUN

consider an array [4,5,6,8] indexed from 0, lets maintain a running sum
(TPES - total possible even subarray)

initial map,

m[0] = represents number of times we have scene even sums
m[1] = represents number of times we have scene odd sums

let the initial values be
m[0]    = 1        , why ?? 
m[1]    = 0

at index 0 sum = 4, possible TPES = 1 {4}                |    m[sum%2] = 1,      m[0] = 2, m[1] = 0    
at index 1 sum = 9, possible TPES = 1 {4}                |    m[sum%2] = 0,      m[0] = 2, m[1] = 1     
at index 2 sum = 15, possible TPES = 2 {4}{6}            |    m[sum%2] = 1,      m[0] = 2, m[1] = 2    
at index 3 sum = 23, possible TPES = 4 {4}{6}{8}{6,8}    |    m[sum%2] = 2,      m[0] = 2, m[1] = 3    

ans = 1 + 0 + 1 + 2 = 4

=====================================================

// PLEASE LET ME KNOW: Whether or not this logic is correct? also how to add code in this editor in order to maintain its structure after publish

//===============================

// CODE BEGINS

#include<bits/stdc++.h>
using namespace std;

int32_t main()
{
    vector<int64_t> a = {4,5,6,8};
    
    int Map[2]              = {},              
        subArraySumEven     = 0,
        totalNoOfSubArray   = 0,
        count               = 0;

    Map[0] = 1;      // base case : if sum == 0 | considered as even

    int sum = 0;
    for(auto i : a)
    {
        sum += i;
        sum %= 2;
        subArraySumEven += Map[sum];
        totalNoOfSubArray += (++count);
        Map[sum%2]++;        
    }
    int subArraySumOdd = totalNoOfSubArray - subArraySumEven;

    cout<<"Number Of Sub Array Sum Odd \t\t"<<subArraySumOdd<<endl;
    cout<<"Number of Sub Array Sum Even \t\t"<<subArraySumEven<<endl;
    cout<<"Total no of possible Subarray were \t"<<totalNoOfSubArray;
}

===============================================================

let me know if this works or not. Both (yes/no) + logic.

Sample Inputs and outputs

INPUT TC-1

[4,5,6,8]

OUTPUT TC-1
Number Of Sub Array Sum Odd             6
Number of Sub Array Sum Even            4
Total no of possible Subarray were      10

INPUT TC-2

[1,1,1]

OUTPUT TC-2

Number Of Sub Array Sum Odd             4
Number of Sub Array Sum Even            2
Total no of possible Subarray were        6