Find number of subarrays with even sum | C ++ program to count number of sub - arrays with even sum using an efficient algorithm Time Complexity - O ( N ) Space Complexity - O ( 1 ) ; Result may be large enough not to fit in int ; ; To keep track of subarrays with even sum starting from index i ; ; If a [ i ] is odd then all subarrays starting from index i + 1 which was odd becomes even when a [ i ] gets added to it . ; If a [ i ] is even then all subarrays starting from index i + 1 which was even remains even and one extra a [ i ] even subarray gets added to it . ; Driver Code
#include <iostream> NEW_LINE using namespace std ; long long countEvenSum ( int a [ ] , int n ) { long long res = 0 ; int s = 0 ; for ( int i = n - 1 ; i >= 0 ; i -- ) { if ( a [ i ] % 2 == 1 ) { s = n - i - 1 - s ; } else { s = s + 1 ; } res = res + s ; } return res ; } int main ( ) { int arr [ ] = { 1 , 2 , 2 , 3 , 4 , 1 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << " The ▁ Number ▁ of ▁ Subarrays ▁ with ▁ even " " ▁ sum ▁ is ▁ " << countEvenSum ( arr , n ) ; return 0 ; }