# Single Number

MathHash TableBit

## # 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, otherwise remove it. At the end, set only has 1 element, so just pop it.

Complexity

time: $O(n)$
space: $O(n)$ (due to set)

def singleNumber(self, nums: List[int]) -> int:
hashset = set()
for num in nums:
if num not in hashset:
else:
hashset.remove(num)
return hashset.pop()

1
2
3
4
5
6
7
8

### # Math

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

Complexity

time: $O(n)$
space: $O(n)$ (due to set)

def singleNumber(self, nums: List[int]) -> int:
return 2*sum(set(nums)) - sum(nums)

1
2

### # 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)$
space: $O(1)$

def singleNumber(self, nums: List[int]) -> int:
res = 0
for num in nums:
res ^= num
return res

1
2
3
4
5