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

Source: leetcode | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

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

Solutions:
class Solution:

	def singleNumber(self, nums):
		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):
		(ones, twos) = (0, 0)
		for i in nums:
			ones = ones ^ i & ~twos
			twos = twos ^ i & ~ones
		return ones


class Solution:

	def singleNumber(self, nums):
		_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):
		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):
		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):
		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):
		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):
		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):
		freq = {}
		for num in nums:
			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):
		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):
		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):
		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)