Largest Gap to the Nearest Greater Value
National Olympiad — Municipal round (2015 season)
Submission name: gap.cpp
Problem summary
For every input value that has a strictly greater input value, find its nearest greater value by magnitude. Output the largest of these differences.
Source clarification. The original source leaves the empty case (fewer than two distinct values) unspecified. This program returns 0 in that case; this is an explicit convention, not a claimed statement requirement.
Input
The count n, followed by n positive integers.
Output
The largest nearest-greater difference.
Constraints
At most 100000 values; every value is positive and below 100000.
Worked example
Input and output for the worked example discussed below.
Input
5 6 7 3 5 10
Output
3
Solution analysis
- Sort the values and remove duplicates. For a distinct value v, the nearest strictly greater value is its immediate successor in this sorted distinct sequence.
- Therefore the required differences are exactly the gaps between adjacent distinct sorted values. Scan them and keep the maximum. The largest distinct value has no greater successor and contributes no candidate.
- The sample becomes [3,5,6,7,10]. Adjacent gaps are 2,1,1,3, so the answer is 3. Repeated copies of a value do not create a zero-gap candidate because greater must be strict.
Why it works
No value lies strictly between two consecutive distinct sorted values, so the successor is the closest allowed greater value. Conversely every value except the maximum has that successor. Thus the set of candidate differences equals the adjacent distinct gaps, whose maximum is the answer.
Watch out. The gap is by numerical value, not by original array position. Equality is not a greater value. The printed source does not define an answer if all values are equal; the implementation uses 0 for this empty candidate set.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int main(){
int count;
cin>>count;
vector<int>values(count);
for(int&value:values){
cin>>value;
}
sort(values.begin(),values.end());
values.erase(unique(values.begin(),values.end()),values.end());
int answer=0;
for(size_t index=1;index<values.size();index++){
// Consecutive distinct sorted values are nearest-greater pairs.
answer=max(answer,values[index]-values[index-1]);
}
cout<<answer<<'\n';
}