Single Number II
First 3 solutions below are from LeetCode solution.
Convert an input array into HashSet and then to compare the tripled sum of the set with the array sum:
def singleNumber(self, nums): return (3 * sum(set(nums)) - sum(nums)) // 2
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 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
x is the single number
result to return, then the bits where
3y+1 times, where . 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.
This method can take more than
3 odd duplicates and return single number
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