354. Missax Guide

(Typical “find the missing element” problem – often appears on many online judges under the name Missax .) 1. Problem statement You are given an integer N ( 1 ≤ N ≤ 10⁶ ) . Then N distinct integers a₁ , a₂ , … , a_N are supplied.

Proof. All numbers of {1,…,N+1} appear either in T (if they are present) or are the missing value m . Hence 354. Missax

Proof. The algorithm first stores missing = S . During the input loop it subtracts each read number a_j from missing . After the loop finishes (Typical “find the missing element” problem – often

read N if N == 0 → finish missing = (N+1)*(N+2)/2 // 64‑bit integer repeat N times read x missing -= x output missing or (XOR version) The algorithm first stores missing = S

int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long N; while (cin >> N) { if (N == 0) break; // end of input // ----- sum based solution ----- long long missing = (N + 1) * (N + 2) / 2; // Σ_{i=1}^{N+1} i for (long long i = 0, x; i < N; ++i) { cin >> x; missing -= x; } cout << missing << '\n'; /* ----- xor based solution (alternatively) ----- long long missing = 0; for (long long i = 1; i <= N + 1; ++i) missing ^= i; for (long long i = 0, x; i < N; ++i) { cin >> x; missing ^= x; } cout << missing << '\n'; ------------------------------------------------- */ } return 0; } The program follows exactly the algorithm proved correct above, conforms to the required I/O format and runs in linear time with constant extra memory. It compiles under any standard C++17 compiler.