Smallest Missing Integer Above a Threshold
National Olympiad — National round (2025 season)
Submission name: smallest.cpp
Problem summary
Find the smallest integer strictly greater than m that is missing from the input sequence.
Input
n m followed by n signed integers.
Output
The smallest absent integer above m.
Constraints
2≤n≤3000000; −13000≤m≤100; −100000≤a[i]≤10^9. The source also lists a[i]−m≤n, although examples exceed it. Original memory limit: 2 MB.
Worked example
Input and output for the worked example discussed below.
Input
6 3 8 -4 1 4 7 2
Output
5
Solution analysis
- Among n+1 candidates m+1,…,m+n+1 at least one is absent, because there are only n input entries. Values outside this candidate interval cannot affect the answer.
- Use a packed Boolean array indexed by offset a[i]−m. Mark valid positive offsets and ignore everything outside 1…n+1. Scan from offset 1 to find the first missing candidate.
- For m=3 and [8,−4,1,4,7,2], present offsets are 1,4,5. The first missing offset is 2, so return 5. The packed vector<bool> needs about 375 KB at maximum n.
Why it works
The pigeonhole bound places the answer inside the candidate interval. Marking records exactly the present candidates; increasing offset order returns the smallest missing one.
Watch out. The answer may be negative. Check offset bounds safely, search strictly above m, and avoid indexing by raw values.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
int threshold;
cin>>n>>threshold;
vector<bool>present(n+2,false);
for(int i=0;i<n;i++){
long long value;
cin>>value;
long long offset=value-threshold;
// Only n+1 candidates are needed by the pigeonhole principle.
if(offset>=1&&offset<=n+1){
present[offset]=true;
}
}
for(int offset=1;offset<=n+1;offset++){
if(!present[offset]){
cout<<threshold+offset<<'\n';
break;
}
}
}