## Monday, June 20, 2016

### Find number of subarrays with even sum - GeeksforGeeks

Find number of subarrays with even sum - GeeksforGeeks
Given an array, find the number of subarrays whose sum is even.
O(n) Time and O(1) Space Method [Efficient]
If we do compute the cumulative sum array in temp[] of our input array, then we can see that the sub-array starting from i and ending at j, has an even sum if temp[] if (temp[j] – temp[i]) % 2 = 0. So, instead of building a cumulative sum array we build a cumulative sum modulo 2 array, and find how many times 0 and 1 appears in temp[] array using handshake formula. [n * (n-1) /2]
`int` `countEvenSum(``int` `arr[], ``int` `n)`
`{`
`    ``// 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`
`    ``int` `temp[2] = {1, 0};`

`    ``// Initialize count.  sum is sum of elements`
`    ``// under modulo 2 and ending with arr[i].`
`    ``int` `result = 0, sum = 0;`

`    ``// i'th iteration computes sum of arr[0..i]`
`    ``// under modulo 2 and increments even/odd count`
`    ``// according to sum's value`
`    ``for` `(``int` `i=0; i<=n-1; i++)`
`    ``{`
`        ``// 2 is added to handle negative numbers`
`        ``sum = ( (sum + arr[i]) % 2 + 2) % 2;`

`        ``// Increment even/odd count`
`        ``temp[sum]++;`
`    ``}`

`    ``// Use handshake lemma to count even subarrays`
`    ``// (Note that an even cam be formed by two even`
`    ``// or two odd)`
`    ``result = result + (temp[0]*(temp[0]-1)/2);`
`    ``result = result + (temp[1]*(temp[1]-1)/2);`

`    ``return` `(result);`
`}`

O(n2) time and O(1) space method [Brute Force]
We can simply generate all the possible sub-arrays and find whether the sum of all the elements in them is an even or not. If it is even then we will count that sub-array otherwise neglect it.
`int` `countEvenSum(``int` `arr[], ``int` `n)`
`{`
`    ``int` `result = 0;`

`    ``// Find sum of all subarrays and increment`
`    ``// result if sum is even`
`    ``for` `(``int` `i=0; i<=n-1; i++)`
`    ``{`
`        ``int` `sum = 0;`
`        ``for` `(``int` `j=i; j<=n-1; j++)`
`        ``{`
`            ``sum = sum + arr[j];`
`            ``if` `(sum % 2 == 0)`
`                    ``result++;`
`        ``}`
`    ``}`

`    ``return` `(result);`
`}`