Proof. The algorithm first stores missing = S . During the input loop it subtracts each read number a_j from missing . After the loop finishes
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.
Proof. All numbers of {1,…,N+1} appear either in T (if they are present) or are the missing value m . Hence
S = (sum of present numbers) + m = T + m Rearranging gives m = S – T . ∎ The algorithm computes missing = S – T . 354. Missax
The input may contain several test cases. Each test case is described as follows
x = 1 xor 2 xor … xor (N+1) xor a1 xor a2 … xor aN Every value that appears twice cancels out, leaving the missing number. Both approaches are linear in time and constant in memory. For each test case
{ 1 , 2 , 3 , … , N+1 } i.e. the list is a permutation of the numbers 1 … N+1 . Your task is to output the missing number. All numbers of {1,…,N+1} appear either in T
N a1 a2 … aN (may be split over several lines) The file ends with a line containing 0 , which must be processed.
All the numbers belong to the set
missing = S – Σ a_j = S – T ∎ For each test case the algorithm outputs the unique missing integer. N+1} is missing
missing = 0 for i = 1 … N+1 missing ^= i repeat N times read x missing ^= x output missing We prove the sum‑based algorithm; the XOR version follows the same line of reasoning. Lemma 1 Let S = Σ_{i=1}^{N+1} i . Let T = Σ_{j=1}^{N} a_j be the sum of the numbers actually present. If exactly one element m of {1,…,N+1} is missing, then S - T = m .
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)