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 ) ; 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
def countEvenSum ( arr , n ) : NEW_LINE INDENT res = 0 NEW_LINE s = 0 NEW_LINE for i in reversed ( range ( n ) ) : NEW_LINE INDENT if arr [ i ] % 2 == 1 : NEW_LINE INDENT s = n - i - 1 - s NEW_LINE DEDENT else : NEW_LINE INDENT s = s + 1 NEW_LINE DEDENT res = res + s NEW_LINE DEDENT return res 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