categories: Code, Interview Question, leetcode, Easy
source: https://leetcode.com/problems/single-number
topics: Bit Manipulation

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

You must implement a solution with a linear runtime complexity and use only constant extra space.

Idea: Bit Manipulation

If we take XOR of zero and some bit, it will return that bit
- a⊕0=a
If we take XOR of two same bits, it will return 0
- a⊕a=0
a⊕b⊕a=(a⊕a)⊕b=0⊕b=b So we can XOR all bits together to find the unique number.

Code:

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