Leetcode 136. Single Number

https://leetcode.com/problems/single-number/

Linear time complexity means O(n) and hence no sorting. Of course we can use a hash table, while it will use O(n) space.

So what is the O(n) O(1) solution? Actually it is based on the two formulas: N XOR N = 0, N XOR 0 = N. Therefore we just XOR them all and the result is the wanted number.

Solution:

# T:O(n) S:O(1)
import operator
class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        return reduce(operator.xor, A)

Run Time: 60 ms