CP83 · 缺失的数字

简单位运算异或时限 1000 ms(参考)
题目描述

给定一个包含 n 个互不相同整数的数组,这些整数取自 0 到 n 共 n+1 个数,恰好缺少一个,找出缺失的那个数。要求 O(n) 时间、O(1) 额外空间(不允许排序或哈希表)。

输入描述

第一行一个整数 n(1 ≤ n ≤ 10^5);第二行 n 个互不相同的整数,取值范围 [0, n]。

输出描述

一行,一个整数:缺失的数字。