# 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:
• space: b/c of set
def singleNumber(self, nums: List[int]) -> int:
st = set()
for num in nums:
if num not in st:
else:
st.remove(num)
return st.pop()


### # Math

Say c is the single number while a and b appear twice. Then .

Complexity:

• time:
• space: 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:
• space:
def singleNumber(self, nums: List[int]) -> int:
res = 0
for num in nums:
res ^= num
return res

Last Updated: 5/13/2020, 7:39:18 AM