One Missing, One Repeated
National Olympiad — National round (2019 season)
Submission name: numbers.cpp
Problem summary
The integers 1 through N are modified by removing A and adding another copy of B, then shuffled. It is known that A=kB for the supplied integer k>1. Find B using little memory.
Input
N and k, followed by the N modified sequence elements.
Output
The duplicated number B.
Constraints
1 < N < 1000000; 1 < k ≤ N; the input has a unique solution; memory limit 2 MB.
Worked example
An independently prepared example for this explanation.
Input
7 3 4 1 7 2 3 2 5
Output
2
Solution analysis
- The original sequence sum is expected=N(N+1)/2. Sum the supplied elements in a streaming pass; there is no need to store them.
- The new sum is expected−A+B. Since A=kB, the missing amount is expected−actual=(k−1)B. Divide this difference by k−1 to recover B exactly.
- For the sample, expected=28 and actual=24. Their difference is 4; k−1 is 2, so B=2. Then A=6, agreeing with the missing number.
Why it works
The only changes to the original sum are subtracting A and adding B. Substituting A=kB proves expected−actual=(k−1)B. Since k>1, division uniquely recovers B. The promised valid input guarantees an integer answer.
Watch out. Use 64-bit arithmetic before multiplying N(N+1); the sum can be about 5·10¹¹. Do not allocate an occurrence array under the small memory limit.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, k;
cin >> n >> k;
long long actual = 0;
for (long long i = 0; i < n; ++i) {
long long value;
cin >> value;
actual += value;
}
// The sum deficit is A-B = (k-1)*B.
long long expected = n * (n + 1) / 2;
cout << (expected - actual) / (k - 1) << '\n';
}