136. Single Number

This is an interesting problem.

Difficulty: Easy

Topics: Array, Hash Table, Bit Manipulation

The array with hash table is easy to solve.

Solution 2 is based on math, which is very smart.

Solution 3 is based on bit manipulation, this one is very tricky. It's based on the XOR operation. Also rely on the property that XOR operation is commutative and associative.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # Solution 1
        # d = defaultdict(int)
        # for n in nums:
        #     if d[n] == 0:
        #         d[n] += 1
        #     else:
        #         d[n] -= 1
        # for key, val in d.items():
        #     if val != 0:
        #         return key
        # return -1
        
        # Solution 2
        # return 2 * sum(set(nums)) - sum(nums)

        # Solution 3
        i = 0
        for n in nums:
            i ^= n
        return i