Single Number

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

# Solution

B/c duplicates are unwanted, we should recognize the correct data structure to use: set, as used in solutions HashSet and Math.

The bit manipulation solution is most elegant.

# HashSet

Add to set if num is not seen yet, o.w. remove it. At the end, set only has 1 element, so just pop it.

Complexity:

  • time: O(n)O(n)
  • space: O(n)O(n) b/c of set
def singleNumber(self, nums: List[int]) -> int:
    st = set()
    for num in nums:
        if num not in st:
            st.add(num)
        else:
            st.remove(num)
    return st.pop()

# Math

Say c is the single number while a and b appear twice. Then 2(a+b+c)(a+a+b+b+c)=c2*(a+b+c)−(a+a+b+b+c)=c.

Complexity:

  • time: O(n)O(n)
  • space: O(n)O(n) b/c of set
def singleNumber(self, nums: List[int]) -> int:
    return 2*sum(set(nums)) - sum(nums)

# Bit Manipulation

^ is the associative & communicative XOR operator. These are its features:

  • 0^a = a
  • a^a = 0
  • a^b^a = (a^a)^b = 0^b = b

Complexity:

  • time: O(n)O(n)
  • space: O(1)O(1)
def singleNumber(self, nums: List[int]) -> int:
    res = 0
    for num in nums:
        res ^= num
    return res
Last Updated: 7/19/2020, 3:45:14 PM