Given a non-empty array of integers, every element appears twice except for one. 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,1]
Output: 1


Example 2:


Input: [4,1,2,1,2]
Output: 4

Source: leetcode | Difficulty: EASY
Tags: Bit manipulation

Data structures

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

Solutions:
class Solution:

	def singleNumber(self, nums):
		l = len(nums)
		if l == 1:
			return nums[0]
		result = 0
		for num in nums:
			result ^= num
		return result


class Solution:

	def singleNumber(self, nums):
		single = 0
		for n in nums:
			single ^= n
		return single


class Solution:

	def singleNumber(self, nums):
		count = 0
		for key in nums:
			count = count ^ key
		return count


class Solution:

	def singleNumber(self, nums):
		result = 0
		for i in nums:
			result ^= i
		return result


class Solution:

	def singleNumber(self, nums):
		res = 0
		for i in range(len(nums)):
			res ^= nums[i]
		return res


class Solution:

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


class Solution:

	def singleNumber(self, nums):
		if not nums:
			return
		s = set(nums)
		t = nums.copy()
		i = 0
		while s and i < len(t):
			if t[i] in s:
				s.remove(t.pop(i))
			else:
				i += 1
		return (set(nums) - set(t)).pop()


class Solution:

	def singleNumber(self, nums):
		nums.sort()
		if len(nums) == 1:
			return nums[0]
		for i in range(0, len(nums), 2):
			if i == len(nums) - 1:
				return nums[i]
			if nums[i] != nums[i + 1]:
				return nums[i]


class Solution:

	def singleNumber(self, nums):
		res = 0
		for num in nums:
			res ^= num
		return res


class Solution:

	def singleNumber(self, nums):
		single_one = {nums[0]}
		for i in nums[1:]:
			if i in single_one:
				single_one.remove(i)
				continue
			else:
				single_one.add(i)
			if single_one == {}:
				single_one.add(i)
		return single_one.pop()


class Solution:

	def singleNumber(self, nums):
		dic = dict()
		for num in nums:
			if num not in list(dic.keys()):
				dic[num] = 1
			else:
				dic[num] += 1
		for (key, val) in list(dic.items()):
			if val == 1:
				return key


class Solution:

	def singleNumber(self, nums):
		mydict = {}
		for i in nums:
			if i not in mydict.keys():
				mydict[i] = 1
			else:
				if mydict[i] >= 2:
					return i
				mydict[i] = mydict[i] + 1
		for (key, value) in mydict.items():
			if value != 2:
				return key


class Solution:

	def singleNumber(self, nums):
		nums.sort()
		for i in range(len(nums)):
			if not (i + 1 < len(nums) and (nums[i] == nums[i + 1] or nums[i] == nums[i - 1])):
				return nums[i]


class Solution:

	def singleNumber(self, nums):
		_dict = {}
		for num in nums:
			try:
				del _dict[num]
			except:
				_dict[num] = True
		return list(_dict.keys())[0]


class Solution:

	def singleNumber(self, nums):
		dic = {}
		ans = 0
		for i in range(len(nums)):
			if str(nums[i]) in dic:
				dic[str(nums[i])] += 1
			else:
				dic[str(nums[i])] = 1
		for num in dic:
			if dic[num] == 1:
				ans = int(num)
		return ans


class Solution:

	def singleNumber(self, nums):
		from collections import Counter
		a = Counter(nums)
		print(a)
		for (k, i) in list(a.items()):
			if i < 2:
				return k