1
$\begingroup$

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 to 0 and evens to 1.
  • iterate through the array.
    • at each index i, do sum = (sum + A[i]) % 2
      • if sum is 0, increment evens, else increment odds
  • Lastly, return (evens * (evens - 1) / 2) + (odds * (odds - 1) / 2)

The algorithm works... I just have no idea how.

$\endgroup$
4
$\begingroup$

Let $S_i$ be the sum of the array upto index $i$. Then we can directly calculate the sum of any contiguous subarray $x_i, x_{i+1}, ..., x_{j}$ using the expression $S_j - S_{i-1}$. This subarray will have even sum only if $S_{i-1}$ and $S_j$ are both even or both odd.

With this in mind, we can count how many even and odd $S_i$ we have and then calculate the number of possible pairs of $S_i$ and $S_j$ that yield an even number. So if we have $e$ even $S_i$ then there are $e \choose 2$ possible pairs. Each pair, corresponds to a different contiguous subarray.

$$ {e \choose 2} = \frac{e!}{(e-2)!2!} = \frac{e * (e-1)}{2} $$

Same holds for the pair of odds.

$\endgroup$
  • $\begingroup$ Welcome to the site! For a moment, I thought you might be one of the two Andreas G.'s I know, but your profile says you're not. $\endgroup$ – David Richerby Jan 28 '18 at 12:54
  • $\begingroup$ Thanks! Yes, I don't think we know each other! :) $\endgroup$ – Andreas G. Jan 28 '18 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.