Find number of subarrays with even sum | Python 3 program to count number of sub - arrays with even sum using an efficient algorithm Time Complexity - O ( N ) Space Complexity - O ( 1 ) ; A temporary array of size 2. temp [ 0 ] is going to store count of even subarrays and temp [ 1 ] count of odd . temp [ 0 ] is initialized as 1 because there a single even element is also counted as a subarray ; Initialize count . sum is sum of elements under modulo 2 and ending with arr [ i ] . ; i ' th ▁ iteration ▁ computes ▁ sum ▁ of ▁ arr [ 0 . . i ] ▁ ▁ under ▁ modulo ▁ 2 ▁ and ▁ increments ▁ even / odd ▁ ▁ count ▁ according ▁ to ▁ sum ' s value ; 2 is added to handle negative numbers ; Increment even / odd count ; Use handshake lemma to count even subarrays ( Note that an even cam be formed by two even or two odd ) ; Driver code
def countEvenSum ( arr , n ) : NEW_LINE INDENT temp = [ 1 , 0 ] NEW_LINE result = 0 NEW_LINE sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum = ( ( sum + arr [ i ] ) % 2 + 2 ) % 2 NEW_LINE temp [ sum ] += 1 NEW_LINE DEDENT result = result + ( temp [ 0 ] * ( temp [ 0 ] - 1 ) // 2 ) NEW_LINE result = result + ( temp [ 1 ] * ( temp [ 1 ] - 1 ) // 2 ) NEW_LINE return ( result ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 2 , 2 , 3 , 4 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " The ▁ Number ▁ of ▁ Subarrays ▁ with ▁ even " " ▁ sum ▁ is " , countEvenSum ( arr , n ) ) NEW_LINE DEDENT