#383. 题目7:找出只出现一次的数

题目7:找出只出现一次的数

题目7:找出只出现一次的数

题目描述
有一个整数数组,其中只有一个数字出现一次,其余每个数字都恰好出现两次。请找出那个只出现一次的数字。要求使用位运算,且时间复杂度为 O(n),空间复杂度为 O(1)。

输入格式
第一行是一个整数 n(1 ≤ n ≤ 10⁵,保证 n 是奇数)。
第二行是 n 个整数,表示数组元素(每个数在 int 范围内)。

输出格式:一个整数,表示只出现一次的那个数。

示例

输入:
5
4 1 2 1 2
输出:
4

提示:利用异或的性质——相同数异或为 0,任何数与 0 异或等于它自己!