136.Single Number

Tags: [bit], [bit_manipulation], [math], [xor]

Com: {t}, {t_review}

Hard: [#]

Link: https://leetcode.com/problems/single-number/\#/description

Given an array 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?

Solution: XOR, Math, Bit Manipulation

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return None
        if len(nums) == 1:
            return nums[0]

        num = nums[0]
        for i in xrange(1, len(nums)):
            num ^= nums[i]

        return num

Note:

• Time complexity = O(n), n is the number of elements in nums.
• Space complexity = O(1).