丢失的数字

述给定整数 n 和一个包含 n - 1 个整数的序列，该序列由区间 [1, n] 内的 n - 1 个互异整数组成。请找出该区间内缺失的唯一整数。

时间限制：1000ms，内存限制：256MB

输入格式

第一行：一个整数 n；

第二行：n - 1 个整数。

输出格式

一个整数，表示丢失的数字。

输入样例#1

6
1 2 5 6 3

输出样例#1

4

输入样例#2

10
7 2 3 9 4 8 1 6 10

输出样例#2

5

数据范围：

1≤n≤2×10⁴ ，输入序列保证合法。

可以使用异或运算来解决这个问题。具体步骤如下：

1. 计算从 1 到 n 的所有整数的异或结果，记为 xor_total。
2. 计算输入序列中所有整数的异或结果，记为 xor_input。
3. 缺失的数字即为 xor_total 和 xor_input 的异或结果。

异或运算有一个重要的性质：对于任何数 x，有 x ^ x = 0，x ^ 0 = x。因此，如果我们有一个数集，我们对它们进行异或运算，那么结果中每一位上的数字都是数集中每个元素在该位上的贡献的总和。如果某个元素出现了偶数次，那么它的贡献为0（因为a ^ a = 0），如果某个元素出现了奇数次，那么它的贡献就是它本身。因此，如果我们有一个数集的所有元素的异或结果，然后我们再异或上另一个数集中的元素（这两个数集的并集为全集），那么结果中缺失的元素就是原来没有的元素。在本题中，我们可以利用这个性质来找出缺失的数字。首先计算从 1 到 n 的所有整数的异或结果 xor_total，然后再计算输入序列中所有整数的异或结果 xor_input，那么缺失的数字就是 xor_total ^ xor_input。这个算法的时间复杂度为 O(n)，满足题目要求的时间限制。