Subarrays with an odd sum
Count the contiguous subarrays whose sum is odd.
Reported in: Deloitte (memory-based)
Input
First line: N. Second line: N integers.
Output
The number of subarrays with an odd sum.
Constraints
1 ≤ N ≤ 10^5.
Example 1
Input:
3
1 3 5
Output:
4Example 2
Input:
4
2 4 6 8
Output:
0Hint: A subarray sum is odd when the two prefix sums around it have different parity. Count odd and even prefixes.