Given anon-emptyarray of integers, every element appearstwiceexcept 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

We could sort it first and find the answer in one pass (time complexity O(nlogn); space complexity O(1)). Or, we can use a hashmap to record the number of appearances to find the number with 1 appearance (time complexity O(n); space complexity O(n)).

Noticing the follow-up requires O(n) time complexity and O(1) space complexity, we would need to use bitwise operators: XOR.

#### XOR

- Commutative: A ⊕ B = B ⊕ A
- Associative: A ⊕ ( B ⊕ C ) = ( A ⊕ B ) ⊕ C
- Identity element: A ⊕ 0 = A
- Self-inverse: A ⊕ A = 0

Therefore, given different numbers as `[a,b,c,a,b]`

, we have

With this being said, all we need to do is to apply XOR to input one by one. Python code is as follows:

```
def singleNumber(self, nums: List[int]) -> int:
return reduce(lambda x,y:x^y,nums)
```