Missing Number
One value from 1 through n is absent from the input list; recover it without sorting.
Problem Summary
Original task summary for this archive page. The official CSES statement is linked in the header instead of being mirrored here.
You should receive every integer from \(1\) through \(n\), except that one value is missing. The task is to determine which value never appears.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
The full set \(1 + 2 + \cdots + n\) has a known sum: \[ \frac{n(n + 1)}{2}. \]
If we subtract the sum of the numbers that were actually provided, the remainder must be the missing value.
That avoids sorting, marking arrays, or any more complicated bookkeeping. A single pass through the input is enough.
Complexity Analysis
Time and memory costs for the approach used in the implementation below.
Time: \(O(n)\)
Memory: \(O(1)\)
C++ Solution
The exact repository source used for this solution page.
#include <cstdint>
#include <iostream>
int main() {
std::int64_t n;
std::cin >> n;
std::int64_t actual_sum = 0;
for (std::int64_t i = 0; i < n - 1; ++i) {
std::int64_t value;
std::cin >> value;
actual_sum += value;
}
const std::int64_t expected_sum = n * (n + 1) / 2;
std::cout << expected_sum - actual_sum << '\n';
return 0;
}
Notes / Pitfalls
Short reminders about edge cases, construction details, or common mistakes.
Compute the sums with 64-bit integers. The formula can overflow a 32-bit type even though the answer itself is small.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.