The Middle Number
Autumn Tournament (2010)
Submission name: middle.cpp
Problem summary
Given three distinct integers a, b and c, print the one that is neither smallest nor largest.
Input
Three integers a, b and c.
Output
The middle value.
Constraints
0 ≤ a, b, c ≤ 10^18; all three values are distinct.
Worked example
Original statement sample, translated without changing its numeric data.
Input
5 16 10
Output
10
Solution analysis
- Put the three values in an array and sort them in increasing order. The desired value is the second array element.
- No arithmetic on the values is necessary. Comparisons avoid overflow even near 10^18. Use long long to store each input value.
- For 5, 16 and 10, sorting produces 5, 10, 16. The second value is 10.
Why it works
Sorting places the unique smallest value first and the unique largest value last. The remaining, second value is therefore exactly the required middle value.
Complexity: O(1) time and O(1) extra space: the input has a fixed number of values.
Watch out. Use a 64-bit type. Do not assume the input is already sorted.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
long long values[3];
cin>>values[0]>>values[1]>>values[2];
// Sorting three values leaves the median at index 1.
sort(values,values+3);
cout<<values[1]<<'\n';
}