Find number of subarrays with even sum | PHP 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 can be formed by two even or two odd ) ; Driver code
< ? php function countEvenSum ( $ arr , $ n ) { $ temp = array ( 1 , 0 ) ; $ result = 0 ; $ sum = 0 ; for ( $ i = 0 ; $ i <= $ n - 1 ; $ i ++ ) { $ sum = ( ( $ sum + $ arr [ $ i ] ) % 2 + 2 ) % 2 ; $ temp [ $ sum ] ++ ; } $ result = $ result + ( int ) ( $ temp [ 0 ] * ( $ temp [ 0 ] - 1 ) / 2 ) ; $ result = $ result + ( int ) ( $ temp [ 1 ] * ( $ temp [ 1 ] - 1 ) / 2 ) ; return ( $ result ) ; } $ arr = array ( 1 , 2 , 2 , 3 , 4 , 1 ) ; $ n = sizeof ( $ arr ) ; echo " The ▁ Number ▁ of ▁ Subarrays ▁ " . " with ▁ even " , " ▁ sum ▁ is ▁ " , countEvenSum ( $ arr , $ n ) ; ? >