Missax: 354.

{ 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.

S = (sum of present numbers) + m = T + m Rearranging gives m = S – T . ∎ The algorithm computes missing = S – T . 354. Missax

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

Proof. The algorithm first stores missing = S . During the input loop it subtracts each read number a_j from missing . After the loop finishes S = (sum of present numbers) + m

(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. By Lemma 2 the value stored in missing after processing the whole test case equals S – T . By Lemma 1 S – T equals the missing element m . Therefore the printed value is exactly m . ∎ Time – each number is read and processed once → O(N) per test case. Memory – only a few 64‑bit variables are kept → O(1) . 6. Reference implementation (C++17) #include <bits/stdc++.h> using namespace std;

N a1 a2 … aN (may be split over several lines) The file ends with a line containing 0 , which must be processed.