Count subarrays with same even and odd elements | C ++ program to find total number of even - odd subarrays present in given array ; function that returns the count of subarrays that contain equal number of odd as well as even numbers ; initialize difference and answer with 0 ; create two auxiliary hash arrays to count frequency of difference , one array for non - negative difference and other array for negative difference . Size of these two auxiliary arrays is ' n + 1' because difference can reach maximum value ' n ' as well as minimum value ' - n ' ; initialize these auxiliary arrays with 0 ; since the difference is initially 0 , we have to initialize hash_positive [ 0 ] with 1 ; for loop to iterate through whole array ( zero - based indexing is used ) ; incrementing or decrementing difference based on arr [ i ] being even or odd , check if arr [ i ] is odd ; adding hash value of ' difference ' to our answer as all the previous occurrences of the same difference value will make even - odd subarray ending at index ' i ' . After that , we will increment hash array for that ' difference ' value for its occurrence at index ' i ' . if difference is negative then use hash_negative ; else use hash_positive ; return total number of even - odd subarrays ; Driver code ; Printing total number of even - odd subarrays
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countSubarrays ( int arr [ ] , int n ) { int difference = 0 ; int ans = 0 ; int hash_positive [ n + 1 ] , hash_negative [ n + 1 ] ; fill_n ( hash_positive , n + 1 , 0 ) ; fill_n ( hash_negative , n + 1 , 0 ) ; hash_positive [ 0 ] = 1 ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] & 1 == 1 ) difference ++ ; else difference -- ; if ( difference < 0 ) { ans += hash_negative [ - difference ] ; hash_negative [ - difference ] ++ ; } else { ans += hash_positive [ difference ] ; hash_positive [ difference ] ++ ; } } return ans ; } int main ( ) { int arr [ ] = { 3 , 4 , 6 , 8 , 1 , 10 , 5 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << " Total ▁ Number ▁ of ▁ Even - Odd ▁ subarrays " " ▁ are ▁ " << countSubarrays ( arr , n ) ; return 0 ; }