Even Products
National Olympiad — Municipal round (2022 season)
Submission name: even.cpp
Problem summary
Count nonempty contiguous subarrays whose product is even.
Input
n, followed by n positive integers.
Output
The number of qualifying subarrays.
Constraints
0 < n < 10000; 0 < a[i] < 1000.
Worked example
An independently prepared example for this explanation.
Input
4 5 3 2 5
Output
6
Solution analysis
- A product is even exactly when at least one of its factors is even. Instead of multiplying anything, remember the most recent even element’s one-based position, initially zero.
- At right endpoint r, all starting positions from 1 through lastEven include that most recent even element. Every later starting position contains only odd elements. Add lastEven to the result.
- In 5,3,2,5, the first two endpoints contribute zero. At the third element, lastEven becomes 3, and endpoints three and four each contribute three, giving six.
Why it works
For any endpoint, a subarray product is even if and only if its start is at most the latest even position. Thus exactly lastEven valid subarrays end there. Summing over endpoints counts every valid subarray exactly once.
Complexity: O(n) time and O(1) extra space.
Watch out. Do not compute products: they can overflow despite the small inputs. Odd runs may have length zero, and an all-odd sequence has answer zero.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
// Algorithm: A product is even exactly when at least one of its factors is even.
using namespace std;
int main(){
int n;
cin>>n;
int lastEven=0;
long long answer=0;
for(int position=1;position<=n;++position){
int value;
cin>>value;
if(value%2==0){
lastEven=position;
}
answer+=lastEven;
}
cout<<answer<<'\n';
}