Average of Even Numbers
National Olympiad — Municipal round (2012 season)
Submission name: average.cpp
Problem summary
Find the arithmetic mean of all even integers in the inclusive interval [m,n].
Input
Two natural numbers m and n.
Output
The mean of the even numbers in the interval.
Constraints
0 < m < n < 2,000,000,000.
Worked example
An independently prepared example for this explanation.
Input
1 6
Output
4
Solution analysis
- Move m upward by one if it is odd. Move n downward by one if it is odd. These are the first and last included even numbers.
- An arithmetic progression has mean equal to the average of its endpoints: (first+last)/2. Consecutive pairs from opposite ends have this same sum.
- In [1,6], the even numbers are 2,4,6. Their mean is (2+6)/2 = 4.
Why it works
Pairing the first and last even numbers, the second and second-last, and so on gives the same sum each time. Consequently the mean is the endpoint average. Since m<n, at least one even integer is present.
Complexity: O(1) time and extra space.
Watch out. Use long long for the endpoint sum, which can exceed signed 32-bit range. The mean is an integer.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
long long first, last;
cin >> first >> last;
// The mean of an arithmetic progression is its endpoint average.
first += first % 2;
last -= last % 2;
cout << (first + last) / 2 << '\n';
}