## Description

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

``````Input: [2,2,1]
Output: 1``````

Example 2:

``````Input: [4,1,2,1,2]
Output: 4``````

## Solution

First of all, need to recognize follow things:

• XOR

XOR is a binary operation, it stands for “exclusive or”, that is to say the resulting bit evaluates to one if only exactly one of the bits is set.

This is its function table:

``````a | b | a ^ b
--|---|------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0``````

This operation is performed between every two corresponding bits of a number.

Example: `7 ^ 10`
In binary: `0111 ^ 1010`

``````  0111
^ 1010
======
1101 = 13``````

Properties: The operation is commutative, associative and self-inverse.

• XOR rules

• any number XOR to itself return 0
• any number XOR to 0 return itself

python code:

``````class Solution:
def singleNumber(self, nums: List[int]) -> int:
single_number = 0
for num in nums:
single_number ^= num
return single_number``````

Golang code:

``````func singleNumber(nums []int) int {
s_num := 0
for _,num := range nums{
s_num ^= num
}
return s_num
}``````