Prefix Sums and Parity
HardPractice library · +30 XPprefix sumsparitycombinatorics
Given an array of N integers, compute the number of contiguous subarrays whose sum is even. A subarray is defined by its start and end indices (inclusive).
Input
The first line contains an integer N. The second line contains N space-separated integers a_1, a_2, ..., a_N.
Output
Print a single integer: the total count of subarrays with an even sum.
Constraints
1 <= N <= 200000 0 <= a_i <= 10^9
Time limit 2 s (native code; slower languages get more)Memory 256 MB16 hidden tests
Example 1
Input
5 1 2 3 4 5
Output
6
Subarrays with even sums: [2], [4], [1, 2, 3], [2, 3, 4], [3, 4, 5], [1, 2, 3, 4, 5]. Total 6.
Example 2
Input
3 2 4 6
Output
6
All subarrays have even sums: [2], [4], [6], [2, 4], [4, 6], [2, 4, 6]. Total 6.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 2 3 4 5
Example 2 input
3 2 4 6