Missing and Duplicated
National Olympiad — National round
Submission name: missing.cpp
Problem summary
The integers 1 through N have been shuffled after removing one value A and inserting a second copy of a different value B. Recover A and B.
Input
N, followed by N integers.
Output
A then B.
Constraints
1 < N < 500000; exactly one value is missing and one duplicated; memory limit 2 MB.
Worked example
An independently prepared example for this explanation.
Input
5 1 5 3 3 4
Output
2 3
Solution analysis
- Accumulate expected minus actual sums S and sums of squares T while streaming input.
- S=A−B and T=A²−B²=S(A+B). Thus A=(T/S+S)/2 and B=A−S.
- All sums of squares fit signed 64-bit at the given bound.
Why it works
The two identities uniquely recover A and B, and S is nonzero because A and B differ.
Complexity: O(N) time; O(1) space.
Watch out. Avoid an integer frequency array: the task has a 2 MB memory limit. Cast before squaring.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The two identities uniquely recover A and B, and S is nonzero because A and B differ.
#include<iostream>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin>>n;
long long s=0,t=0;
for(long long i=1;i<=n;i++){
long long x;
cin>>x;
s+=i-x;
t+=i*i-x*x;
}
long long a=(t/s+s)/2;
cout<<a<<' '<<a-s<<'\n';
}