Use a set to track numbers. If a number is already in the set, remove it; otherwise, add it. The single remaining element is the answer.
XOR all elements together. Since a ^ a = 0 and a ^ 0 = a, all duplicate pairs cancel out, leaving only the single number.
""" 0136.1 - Solution 1 - Hash Set Approach """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def singleNumber(self, nums: List[int]) -> int:
"""Single Number Function"""
seen = set()
for num in nums:
if num in seen:
seen.remove(num)
else:
seen.add(num)
return seen.pop()
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().singleNumber([2, 2, 1]))
print(Solution().singleNumber([4, 1, 2, 1, 2]))
print(Solution().singleNumber([1]))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0136.2 - Solution 2 - XOR Bit Manipulation """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def singleNumber(self, nums: List[int]) -> int:
"""Single Number Function"""
result = 0
for num in nums:
result ^= num
return result
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().singleNumber([2, 2, 1]))
print(Solution().singleNumber([4, 1, 2, 1, 2]))
print(Solution().singleNumber([1]))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()