So I found a solution to this problem here http://marcodiiga.github.io/number-of-even-sum-subarrays but I am unsure of exactly how it works. I get the premise that in order to have an even sum it must be even or even + even or odd + odd. However, I am not sure how this person manages to take into account the fact that these subarrays need to be contiguous and how just tracking the number of cumulative sums that are even/odd as you iterate through the array is good enough
Outlining his algorithm:
- initialize
sum
,odds
to0
andevens
to 1. - iterate through the array.
- at each index
i
, dosum = (sum + A[i]) % 2
- if
sum
is 0, incrementevens
, else incrementodds
- if
- at each index
- Lastly, return
(evens * (evens - 1) / 2) + (odds * (odds - 1) / 2)
The algorithm works... I just have no idea how.