Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:


Input: [2,2,3,2]
Output: 3


Example 2:


Input: [0,1,0,1,0,1,99]
Output: 99

Difficulty: interview

Starter code:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def singleNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         a = set(nums)
         a = sum(a)*3 - sum(nums)
         return int(a/2)

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


class Solution:
     def singleNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         ones, twos = 0, 0
         for i in nums:
             ones = ones ^ i & ~twos
             twos = twos ^ i & ~ones
         return ones


class Solution:
     def singleNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         _dict = {}
         for num in nums:
             if num not in _dict:
                 _dict[num] = 1
             elif _dict[num] == 1:
                 _dict[num] += 1
             else:
                 del _dict[num]
         return list(_dict.keys())[0]

class Solution:
     def singleNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         zero = 0
         one = 0
         
         for num in nums:
             one, zero = (one ^ (num & zero)) & ~(~zero & one & num), (zero ^ num) & ~(~zero & one & num)
         return zero

class Solution:
     def singleNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         ans = 0
         for i in range(32):
             count = 0
             for num in nums:
                 if ((num >> i) & 1):
                     count += 1
             ans |= ((count%3) << i)
         if ans >= 2**31:
             ans -= 2**32
         return ans

class Solution:
     def singleNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         a = b = 0
         for c in nums:
             a, b = a&~b&~c|~a&b&c, ~a&b&~c|~a&~b&c
         return a|b

class Solution:
     def singleNumber(self, nums):
         dict = {}
         for i in nums:
             if i in dict:
                 dict[i] = dict[i] + 1
             else:
                 dict[i] = 1
         for i in list(dict.keys()):
             if dict[i] == 1:
                 return i
         return -1


class Solution:
     def singleNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         nums.sort()
         if len(nums)<3: return nums[0]
         for i in range(0,len(nums)-1,3):
             if nums[i]!=nums[i+2]: return nums[i]
         return nums[-1]

class Solution:
     def singleNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums:
             return 0
         
         seen = set([])
         counts = {}
         for num in nums:
             if num in seen:
                 counts[num] += 1
             else:
                 counts[num] = 1
                 seen.add(num)
         
         for key in counts:
             if counts[key] == 1:
                 return key
         
         return 0

class Solution:
     def singleNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         '''
         dic = {}
         for num in nums:
             if num in dic and dic[num] == 2:
                 del dic[num]
             else:
                 dic[num] = dic.get(num, 0) + 1
         return [k for k in dic.keys()][0]
         '''
         #return (sum(set(nums))*3-sum(nums))//2
         one, two = 0, 0
         for num in nums:
             one, two = (~two&one&~num)|(~two&~one&num), (two&~one&~num)|(~two&one&num)
         return one


class Solution:
     def singleNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         a = b = 0
         for c in nums:
             a, b = a&~b&~c|~a&b&c, ~a&b&~c|~a&~b&c
         return b

class Solution:
     def singleNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         """
         count frequency of each element
         """
         freq = {}
         for num in nums: #store frequency of each element in the list
             freq[num] = freq.get(num, 0) + 1
         
         for num, frequency in list(freq.items()):
             if frequency == 1:
                 return num


class Solution:
     def singleNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         res = {}
         for i in nums:
             if str(i) not in res:
                 res[str(i)] = 1
             else:
                 res[str(i)] +=1
         for i in res:
             if res[i]==1:
                 return int(i)


class Solution:
     def singleNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         counts = {}
         for num in nums:
             if num not in counts:
                 counts[num] = 1
             else:
                 counts[num] += 1
         for k, v in list(counts.items()):
             if v == 1:
                 return k


class Solution:
     def singleNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums)==1:
             return nums[0]
         
         seen=set()
         
         for a in nums:
             if a not in seen:
                 seen.add(a)
         
         s1 = sum(nums)
         s2 = sum(seen)
         
         return int(s2 - (s1-s2)/2)