# Single Number II

MathHash TableBit

## # Problem ## # Solution

### # HashSet

Convert an input array into HashSet and then to compare the tripled sum of the set with the array sum:

$3 \times (a + b + c) - (a + a + a + b + b + b + c) = 2c$

Complexity

time: $O(n)$
space: $O(n)$

def singleNumber(self, nums):
return (3 * sum(set(nums)) - sum(nums)) // 2


### # HashMap

from collections import Counter
def singleNumber(self, nums):
hashmap = Counter(nums)

for k in hashmap.keys():
if hashmap[k] == 1:
return k


## # Follow Up

Can you solve it using constant space?

We then have to use some clever bit manipulation methods. Both methods below take linear time and constant space.

### # Digital Logic

A good explanation (opens new window) on the following code using digital logic.

def singleNumber(self, nums: List[int]) -> int:
seen_once = seen_twice = 0

for num in nums:
seen_once = ~seen_twice & (seen_once ^ num)
seen_twice = ~seen_once & (seen_twice ^ num)

return seen_once


### # Count Occurrences

If x is the single number result to return, then the bits where x are 1 occur 3y+1 times, where $y \ge 0$. The same case happens for 0 bits of x but doesn't make a difference on res so neglected.

Note that the highlighted line is used in place of the line below for other languages, due to Python's unbound int.

#### # Extension

This method can take more than 3 odd duplicates and return single number res.

def singleNumber(self, nums: List[int]) -> int:
res = 0
for i in range(32):
cnt = 0
for j in range(len(nums)):
if nums[j] & (1 << i) != 0:
cnt += 1
res = res | ((cnt % 3) << i)
# return res
return res if res in nums else res - 2**32