[leetcode]Single Number 비트 XOR연산

• 1 4
• -3 * 104 4
• Each element in the array appears twice except for one element which appears only once.

class Solution:
    def singleNumberBySet(self, nums: List[int]) -> int:
        seen = set()
        for num in nums:
            if num in seen:
                seen.remove(num)
            else:
                seen.add(num)
        return seen.pop()

그런데 문제의 의도는 비트 XOR연산이었다.

a ^ a = 0 (같은 수끼리 XOR 하면 0) a ^ 0 = a (어떤 수든 0과 XOR하면 자기 자신) XOR 연산은 교환법칙과 결합법칙이 성립. 모든 짝이 있는 수들은 XOR 연산으로 상쇄되어 0이 되고, 홀로 있는 수만 남게 됨. 시간 O(n), 공간 O(1)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

#leetcode #비트연산 #XOR