P1469 找筷子

题目描述

CX 小朋友找出了餐厅中所有的筷子，但这些筷子长短不一。筷子需要长度一样的才能组成一双。

现在筷子数量为奇数，并且只有一只筷子是落单的，其余都成双。请你找出这只落单筷子的长度。

输入格式

第一行是一个整数 n，表示筷子的数量。

第二行有 n 个整数，第 i 个整数表示第 i 根筷子的长度 a_i。

输出格式

输出一行一个整数，表示落单筷子的长度。

输入样例

9
2 2 1 3 3 3 2 3 1

输出样例

2

数据范围

• 对于 30% 的数据，n <= 100000。
• 对于 100% 的数据，1 <= n <= 10000001，1 <= a_i <= 1000000000。

提示

本题空间限制较小，不能把所有数据都存进数组。

可以利用异或运算：

• x ^ x = 0
• x ^ 0 = x
• 异或满足交换律和结合律

把所有筷子长度依次异或起来，成双出现的长度会互相抵消，最后剩下的就是落单筷子的长度。