Even sum subarrays

Given an array of integers, count the number of contiguous subarrays with an even sum. You may assume that the array is non-empty, and contains only non-negative integers.

This is , so the shortest code in bytes wins.

Test Cases

Input -> Output
 -> 0
 -> 1
[3, 5] -> 1
[6, 2] -> 3
[2, 4, 5] -> 3
[7, 4, 0, 5, 8] -> 6
[4, 8, 7, 9, 5] -> 7
[1, 9, 1, 0, 4] -> 7
[7, 5, 2, 1, 4, 8] -> 9
[0, 6, 6, 5, 3, 3, 8] -> 13
[8, 5, 9, 4, 5, 1, 0] -> 16
• Fastest algorithm: prepend 0, cumulative sum, each number mod 2, then count zeros (n0) and ones (n1) and calculate n0*(n0-1)/2+n1*(n1-1)/2. Probably not so appealing for golf though. Nov 26 '21 at 5:14
• @Bubbler Imo your insight is the most interesting thing about the problem. It took me a minute to see why it was true -- might be worth an answer with an explanation even if it's not a golf. Nov 26 '21 at 6:56
• On the other hand, for counting odds the formula becomes a lot simpler: n0*n1. Nov 26 '21 at 20:17

Python 3.8 (pre-release), 57 bytes

f=lambda S,p=1:S>[]and f(S[1:])+sum((p:=p^s%2)for s in S)

Try it online!

Similar to brute-force method below but should have better complexity.

Python 3, 57 bytes

f=lambda S:S>[]and~sum(S)%2+f(S[1:])+f(S[:-1])-f(S[1:-1])

Try it online!

This is a brute force method based on inclusion-exclusion. Also works on Python2.

Python 3, 60 bytes

f=lambda S,e=0,i=0:e+(S>S[:i]and f(S,[e+1,i-e][S[i]&1],i+1))

Try it online!

This loops over the right ends of possible subarrays keeping the number of non empty even summing subarrays in e. The number of odd summing subarrays is implicit in i-e (i is the loop index). As we move i to the right we update e by incrementing if we pass through an even element and by replacing with the current odd summing number if we pass through an odd element. The sum of all es is then output.

Correctness and connection with @Bubbler's closed formula

This is a routine combinatorial partition. To count all (non-empty) contiguous subarrays of S with even sum (cswes) we split the set of all cswes into all cswes ending at S(1), all cswes ending at S(2) etc. and add the sizes of these sets instead. If e(n) is the size of the set of cswes ending at S(n) then depending on the parity of S(n+1) we have S(n+1) even ~> e(n+1)=e(n)+1 and S(n+1) odd ~> e(n+1)=o(n) where o(n) is the number of contiguous subarrays with odd sum ending at S(n). Obviously, o(n)+e(n)=n. And with that we have got all the pieces used by the algorithm.

Now to connect with Bubbler's formula let us reinterpret what we are doing when going from e(n) to e(n+1). If S(n+1) is even then we "increment a counter", more specifically, "the active counter". There is also an "inactive counter" which is, err, inactive. If S(n+1) is odd then we "swap the active and inactive counters". Which of the two counters is currently active, i.e. in e depends on the cumulative parity of S up to the current position. The counter that started out as e(0) therefore counts from 0 to n0 (excl) where n0 is as defined by Bubbler and the counter that started out as o(0) counts from 0 to n1. The algorithm adds all the steps together. Therefore, using the well-known summation formula 1+2+...+n = n(n+1)/2 we recover Bubbler's formula.

For reference, here is Bubbler's relevant comment in full:

Fastest algorithm: prepend 0, cumulative sum, each number mod 2, then count zeros (n0) and ones (n1) and calculate n0*(n0-1)/2+n1*(n1-1)/2. Probably not so appealing for golf though. – Bubbler

Python 2, 57 bytes

z=1
for x in input():z+=1j+1-x%2*2*z%1j
print abs(z*z)//4

Try it online!

Thanks to dingledooper for saving 2 bytes with z%1j in place of z.real!

58 bytes

z=p=1
for x in input():p*=1|x%-2;z+=1j+p
print abs(z*z)//4

Try it online!

59 bytes

t=e=o=0
for x in input():e+=1;exec"e,o=o,e;"*x;t+=e
print t

Try it online!

59 bytes

n=0;a=1
for x in input():n+=1;a+=1-x%2*2*a
print a*a+n*n>>2

Try it online!

59 bytes

p,t=l=[0,0]
for x in input():l[p]+=1;p^=x%2;t+=l[p]
print t

Try it online!

All these solutions iterate through the list just once. They're based on Bubbler's observation that the output can be expressed in terms of the numbers $$\(e,o)\$$ of even and odd entries in the cumulative sum as:

$$\frac{e(e+1)+o(o-1)}{2}$$

This is because a sub-list has even sum if and only if its start and end indices correspond to elements of the same parity in the cumulative sum. The number of ways to choose two even or two odd elements in the cumulative sum is $$\\binom{c}{2}\$$, that is $$\c(c-1)/2\$$, where $$\c\$$ is their count. For evens, we need to either prepend a 0 to the cumulative sum or increase the count by 1 to account for the initial total being 0 which is even.

Python, 52 bytes

f=lambda l,b=-1:l>[]and~sum(l)%2+f(l[1:],0)+f(l[:b])

Try it online!

Inspired by loopy walt's inclusion-exclusion approach. Thanks to loopy walt for -2 bytes!

We want to recursively reach all contiguous sublists of l to count those with even sum. We do this by repeatedly removing either the start (first) or end (last) element. But, this generates duplicate sublists because they can be reached via removals in different orders, like start then end versus end then start.

So, we guarantee that we do all start removals before any end removals. That is, once we remove the end, we no longer remove the start. We use a flag b for whether start removals are allowed, which starts at -1 and is set to 0 after an end removal. When b is 0, end removals are replaced with removing the entire list, which effectively cuts off that branch. This gives a quadratic runtime.

• I think you can save 2 bytes on the second last one by using z%1j instead of z.real. Nov 28 '21 at 9:09
• @dingledooper That's a nice trick for Python 2 that looks rather handy for dealing with complex numbers.
– xnor
Nov 29 '21 at 8:28
• -2 and better complexity tio.run/##JU3NCoMwDL7vKXoZtKwDW50/BfcipYeKikLsZNONXfbqXUxLSr6/… Nov 29 '21 at 8:50
• @loopywalt Nice one! With all the golfs where I've wanted l[:-k] to remove the last k elements but it broke at k=0, it's cool to have one where it's good that it works like that.
– xnor
Nov 29 '21 at 22:29
• If only it were just golfing! In my experience it's just as bad with "serious" programming. Anyway, well done! I expected a small or no improvement. -5 with reasonable runtime, clean output and Python2/3 feels massive. Dec 3 '21 at 18:50

05AB1E, 4 bytes

ŒOÈO

Explanation:

Œ     # Get the sublists of the (implicit) input-list
O    # Sum each inner list
È   # Check for each whether it's even
O  # Take the sum to get the amount of truthy results
# (after which this is output implicitly as result)
• +1 for a program that's pronounced "oh ee oh ee oh" :D Nov 26 '21 at 17:12

APL (Dyalog Unicode), 15 13 bytes

+/~2|∊+\¨,⍨\⎕

Try it online!

,⍨\⎕: Reversed prefixes of the input.
+\¨: For each reversed prefix, get the cumulative sums.
: Flatten into a vector of sums.
~2|: For each sum, is it even?
+/: Take the sum.

Slightly longer, but more interesting alternative:

+/,∘.(≤⍱2|-)⍨+\2+0,⎕

Try it online!

0,⍵: Prepend a 0 to the input.
2+: Add 2 to each number. This makes sure all values are positive while not changing any subsequences parities.
+\ Take the cumulative sum. Because the vector contained only positive numbers this is strictly increasing.
∘.( )⍨: Make a table by applying the inner function between all pairs of values.
+/,: Flatten the table and sum all values.

The inner function uses NOR () and might be a bit easier to understand if rewritten with AND ():

(a≤b)⍱(2|a-b) ≡ (~a≤b)∧(~2|a-b) ≡ (a>b)∧(a-b is even)

The a>b makes sure each subsequence is only counted once.

f a=sum[gcd 2s-1|s<-scanl1(+)=<<scanr(:)[]a]

Try it online!

Ruby, 59 ... 37 bytes

->l{*q=r=0,-1;l.sum{|n|q[r^=n%2]+=1}}

Try it online!

Finally found the time to implement Bubbler's advice.

• Can delete the |x| for -3. Nov 26 '21 at 16:28

x86-64 machine code, 21 bytes

31 c9 f7 e1 ff c1 f6 07 01 74 02 87 d1 01 c8 af ff ce 75 f0 c3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the address of an array of 32-bit integers in RDI and the length of the array in RSI.

Assembly:

.text
.global essa
.intel_syntax noprefix
essa:
xor ecx, ecx    #
mul ecx         # Initialise ECX, EAX, and EDX to 0.
repeat:
# EAX holds the running total of even-sum subarrays.
# ECX holds the number of even-sum subarrays ending at the current position.
# EDX holds the number of odd-sum subarrays ending at the current position.
inc ecx                 # Increment the even count.
test BYTE PTR [rdi], 1  # Check the low bit of the current number.
jz skip                 # Jump if the low bit is 0.
xchg ecx, edx           # (Executed if odd) Swap the counts.
skip:
add eax, ecx            # Add the even count to the running total.
scasd                   # Advance to the next number, and perform an unnecessary comparison.
dec esi                 # Count down from the length of the array.
jnz repeat              # Jump back if there is more to be processed.
ret                     # Return.
• Nice one! You can -1 if you're willing to use a custom calling convention and take length in rcx, then use loop instead of dec esi / jnz. Nov 28 '21 at 19:59

Jelly, 5 bytes

Ẇ§2ḍS

Try it online!

Ẇ     # Sublists
§    # Sum (vectorised)
2ḍ  # Is divisisible by 2? (vectorised)
S # Sum (non-vectorising)

J, 17 bytes

1#.1#.(0=2|+/)\\.

Try it online!

• (0=2|+/) Is sum even...
• \\. For each suffix list of each prefix list (so all sublists)? Returns a 0-1 matrix, and now we want to sum all the elements...
• 1#. Sum the rows...
• 1#. And sum the resulting list of sums.
• +/+/(0=2|+/)\\. NB. Saves 2 bytes Nov 26 '21 at 19:49
• @RichardDonovan That’s a snippet rather than a function so illegal under site rules Nov 26 '21 at 20:49

Husk, 8 7 bytes

#ȯ¬%2ΣQ

Try it online!

Explanation

Q  # consecutive subsequences
#        # count elements by
ȯ       # composed function
¬      # not
Σ   # sum
%2    # mod 2

-1 bytes thanks to ovs

JavaScript (ES6),  44  41 bytes

This is inspired by Bubbler's comment, but updates the sum $$\n_0(n_0-1)/2+n_1(n_1-1)/2\$$ on the fly rather than computing it afterwards. The number of 0's and 1's are stored in a and a respectively, with a[] initialized to [1,0].

a=>a.map(c=>t+=a[p^=c&1]++,a=[1,p=t=0])|t

Try it online!

Japt, 5 bytes

ãx èv

Try it

ãx      - subarrays reduced
èv   - number of evens

g l=sum[1|t<-scanr(:)[]l>>=scanl1(+),even t]

Try it online!

• thanks to @ovs for reminding me there's already an even function in Haskell (3 Bytes saved).
• saved 3 more bytes inspired by @Lynn answer and tip for golfing in Haskell
sum          Total of
[1|t<-       * list comprehension counting:
scanr(:)[]l    -tails
>>=            - concatMapped to
scanl1(+)      - cumulative sum
,even t]       ? that satisfy the requirements

Old recursive version

g[]=0
g l=sum[1|t<-scanr1(+)l,even t]+g(init l)
g[]=0            empty list has 0 even sums
g l=             list has :
sum              > number of results found in:
even t             valid tails
t<-scanr1(+)l      directly reduced by +
+g(init l)       > + results of inits
• even t saves 3 bytes
– ovs
Nov 26 '21 at 16:39
• Ahh I thought about it but I forgot to use it while golfing, thanks @ovs Nov 26 '21 at 16:49

Wolfram Language (Mathematica), 36 34 bytes

Tr[1-Mod[Tr/@Subsequences@#,2]]-1&

–2 bytes from @alephalpha

Try it online!

There is an EvenQ test in Mathematica, but alephalpha's use of Mod saves 2 bytes relative to it:

Count[Tr/@Subsequences@#,_?EvenQ]-1&

Alternative 34-byte function from @att:

Count[{a__/;2∣+a}]@*Subsequences
• -2 bytes Nov 26 '21 at 12:41
• alternative 34 bytes
– att
Nov 28 '21 at 5:10
• @att When you paste your code into TIO or CodeGolfSE, how do you get the MMA special characters to display as special characters? E.g., when I recreate your code in my MMA front end, I see the special character. However, when I paste it into TIO or CodeGolfSE, I get \[Divides] instead of the 3-byte gyph. I've had this issue with other MMA-specific glyphs as well. Nov 28 '21 at 5:48
• @theorist I find it's quicker to compare byte counts of different approaches when typed directly in TIO, so I usually just look up the character code or copy the symbol from an existing post (e.g. the tips thread contains quite a few). I've also used this site when copying out of MMA.
– att
Nov 28 '21 at 6:02
• @att Yeah, I've been doing the same thing—trying to find the glyph in another post and copying it. So thanks for that link which, for most glyphs, will allow me to do that without the searching. But what about glyphs that site can't convert, like the superscript T for \[Transpose] (reference.wolfram.com/language/ref/character/Transpose.html)? MMA gives the Unicode value (F3C7), but I've not been able to find a site that converts Unicode values like that to glyphs. And likewise the superscript H for\[HermitianConjugate] (Unicode: F3CE), etc. Nov 28 '21 at 7:07

R, 61 57 bytes

Or R>=4.1, 50 bytes by replacing the word function with \.

-4 bytes thanks to @Dominic van Essen.

function(a,b=diffinv(a)%%2,+=sum,z=+!b,o=+b)0:z+0:o-z-o

Try it online!

Using @Bubbler's formula.

Without it:

R, 64 bytes

Or R>=4.1, 57 bytes by replacing the word function with \.

function(a){for(i in seq(!a))for(j in 1:i)F=F+!sum(a[j:i])%%2;F}

Try it online!

• Don't forget about diffinv... Nov 26 '21 at 16:33
• @DominicvanEssen, right! Forgot again! :@ Nov 26 '21 at 20:01
• 46 bytes Nov 27 '21 at 14:21
• @Giuseppe that's a nice one! I think it deserves a separate answer. Nov 27 '21 at 17:21
• posted! and even managed to shave off another byte. Nov 28 '21 at 5:01

Vyxals, 6 bytes

ÞSḢƛ∑₂

Try it Online!

Thanks to Lyxal for this version.

ÞS     # Sublists
Ḣ    # Remove the empty list at the start
ƛ   # Map to...
∑₂ # Even sum?
# (s flag) sum of all

Vyxal, 8 bytes

ÞS'∑₂;L‹

Try it Online!

ÞS       # Sublists (Including empty array :( )
'  ;   # Filtered by...
∑     # Sum...
₂    # Is even
L‹ # Length of this -1 (Because empty array)
• Try it Online! for 7 Nov 26 '21 at 3:05
• Nice flag abuse :P Nov 26 '21 at 3:07
• Try it Online! for 6 porting jelly Nov 26 '21 at 3:12

Perl 5 + -pal, 56 bytes

$"="+";$_=map{//;grep!(1&eval"@F[$'..$_]"),$_..$#F}0..@F

Try it online!

Perl 5 + -pal -MList::Util+(sum), 46 bytes

$_=map{//;grep!(1&sum@F[$'..$_]),$_..\$#F}0..@F

Try it online!

ayr, 11 bytes

Thanks to ovs's method.

+/|2|,+\\.I

Explanation

I is the input (eg 6 2) passed through the command line.

\.  Suffixes decreasing in length
+\    Cumulative sum of each
,      Flatten
2|       Mod 2
|         Not this (is the number divisible by 2?)
+/          Sum; count number of even elements

R, 45 bytes

function(a,x=table(diffinv(a)%%2))x%*%(x-1)/2

Try it online!

Uses Bubbler's observation and pajonk's test harness.

Retina, 42 27 bytes

.\B|\D

Yd01
Cw(0|10*1)+

Try it online! Link includes test cases. Edit: Saved 15 bytes thanks to @m90. Explanation:

.\B|\D

Delete anything that's not the last digit of an integer.

Yd01

Reduce modulo 2.

Cw(0|10*1)+

Count the number of overlapping matches with an even number of 1s.

• Improvement: the last regex can be changed to (0|10*1)+.
– m90
Dec 3 '21 at 16:57
• @m90 Wow I feel such a fool now...
– Neil
Dec 3 '21 at 17:18

JavaScript (Node.js), 89 bytes

f=x=>0 in x&&f(x.slice(1))+x.filter((_,i)=>~x.slice(0,i+1).reduce((s,y)=>s+y,0)&1).length

Try it online!

Factor + math.unicode, 34 bytes

[ all-subseqs [ Σ even? ] count ]

Try it online!

Scala, 52 bytes

_.tails.flatMap(_.inits)count(x=>x.size>0&x.sum%2<1)

Try it online!

This is a naive answer, but it didn't seem as if Bubbler's approach would be shorter, so I went with this. _.tails.flatMap(_.inits) first gets all subarrays that stretch to the end, then all the prefixes of those subarrays to get all subarrays of the original array.

Charcoal, 23 20 bytes

ＩΣＥ²↨¹…№﹪Ｅ⊕Ｌθ↨¹…θλ²ι

Try it online! Link is to verbose version of code. Explanation: Uses @Bubbler's formula.

²                    Literal 2
Ｅ                     Map over implicit range
θ           Input list
Ｌ            Length
⊕             Incremented
Ｅ              Map over implicit range
θ       Input list
…        Truncated to length
λ      Inner index
↨¹         Converted from base 1 i.e. summed
﹪               Vectorised modulo
²     Literal 2
№           ι    Count the number of 0s or 1s
…                 Exclusive range from 0
↨¹                  Converted from base 1 i.e. summed
Σ                      Take the sum
Ｉ                       Cast to string
Implicitly print

Each contiguous subarray with an even sum must start and end at a point where the cumulative sums are either both even or both odd. The positions of these sums don't matter, only their counts do. The number of sums for a given count is then simply n(n-1)/2, since a given sum can't start and end at the same point. This is readily calculated as the sum of the exclusive range from 0 to n. (Both these sums are implemented as base conversion from base 1 since that returns 0 for an empty list whereas Sum returns None.)

Excel, 130 97 bytes

-33 bytes applying Bubbler's formula

=LET(x,COUNT(A1#),a,SEQUENCE(x),b,SUM(MOD(MMULT(A1#,(a<=TRANSPOSE(a))*1),2)),b*(b-1-x)+(x^2+x)/2)

Rearranged Bubbler's formula to use the number of 1s and size of the original array (instead of the number of 0s). Multiplies the array by an upper triangular matrix to calculate the cumulative sums.

Original Answer not using Bubbler's method

=LET(x,COUNT(A1#),a,SEQUENCE(1,x^2)-1,b,MOD(a,x)+1,c,INT(a/x)+1,d,SEQUENCE(x),SUM(1-MOD(MMULT(A1#,FILTER((d>=b)*(d<=c),b<=c)),2)))

Explanation

Since Excel formulas don't really have loops, I have to get creative with in sequences in two dimensional space.
LET(x,COUNT(A1#), : x = number of elements
a,SEQUENCE(1,x^2)-1, : a = [0..x^2]
b,MOD(a,x)+1, : b = array of indices of the first items to be summed
c,INT(a/x)+1, : c = array of indices of the last items to be summed
d,SEQUENCE(x), : d = [1..x]
FILTER((d>=b)*(d<=c),b<=c)) : array containing all permutations of possible consecutive sums indicated by 1 in the elements to be summed
MMULT(A1#,~,2) : use matrix multiplication to determine all the sums of consecutive elements
SUM(1-MOD(~,2))) : count the sums where the sum mod 2 = 0

C (gcc), 77 $$\\cdots\$$ 67 65 bytes

t;p;f(a)int*a;{for(int b[]={1,t=p=0};~*a;)t+=b[p^=*a++&1]++;t=t;}

Try it online!

Saved 9 11 bytes thanks to Arnauld!!!

Inputs a pointer to an array of non-negative integers terminated by $$\-1\$$ (because pointers in C carry no length info).
Returns the number of contiguous subarrays with an even sum.

• Would a -1 terminated list as input be acceptable? (Using ~*a and *a++, saving 2 bytes.) Nov 27 '21 at 15:21
• @Arnauld Hooray - for the win! :D Nov 27 '21 at 23:11

TI-Basic, 27 bytes

fPart(.5cumSum(Ans
{2sum(Ans),1+sum(not(Ans
sum(Ans.5(Ans-1

Uses Bubbler's formula. Takes input in Ans. Output is stored in Ans and displayed.

• How did you get the count of 27 bytes? I don't know TI-Basic but, at least on the face of it, it looks like 57 bytes. Nov 27 '21 at 1:50
• @theorist TI-Basic is a tokenized language, so fPart(, Ans, sum(, and not( are tokens which are worth 1 byte, and cumSum( is a token that is worth 2 bytes. Learn more about TI-Basic tokens here. Nov 27 '21 at 2:31
• Thanks for the explanation. IIUC, you determine the number of bytes by the size of the command when it's stored in RAM, rather than the size of the command you need to input. But that makes me curious. Consider, say, the Mathematica command "Sin", or the C++ command "for". Currently, we count those both as 3 bytes, because that's the number of bytes needed to input them. But would it necessarily be the case that, when those commands are stored in RAM, they each actually take up 3 bytes? If not, then are we counting bytes for tokenized vs. non-tokenized languages inconsistently? Nov 27 '21 at 3:12
• "Currently, we count those both as 3 bytes, because that's the number of bytes needed to input them." in this case, we also count the number of bytes needed to input the program into a TI calculator. I see no inconsistency here @theorist Nov 27 '21 at 11:56
• @theorist there is already a consensus on how to score TI-Basic answers: codegolf.meta.stackexchange.com/a/4764/98541 Nov 29 '21 at 10:58

Pari/GP, 47 bytes

a->sum(i=1,#a,sum(j=i,#a,!(vecsum(a[i..j])%2)))

Try it online!

APL (Dyalog Classic), 25 bytes

{+/∊{~2|+/¨⍵}¨{,\⌽⍵}¨,\⍵}

Try it online!

Burlesque, 11 bytes

su{++2dv}fl

Try it online!

su    # All Subsequences
{++   # Sum
2dv  # Divisible by 2
}fl   # Number matching filter