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. 354. Missax
Proof. All numbers of {1,…,N+1} appear either in T (if they are present) or are the missing value m . Hence x = 1 xor 2 xor … xor
All the numbers belong to the set
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 list is a permutation of the numbers 1 … N+1
(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.
N a1 a2 … aN (may be split over several lines) The file ends with a line containing 0 , which must be processed.
