[Leetcode] 136. Single Number

문제

https://leetcode.com/problems/single-number/description/?envType=study-plan-v2&envId=top-100-liked

풀이

constant extra space만을 이용하도록 하는 방법이 도저히 떠오르지 않았고, 처음에는 아래와 같은 풀이를 제출했다. AC를 받을 수는 있었다.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        num_set=set()
        for num in nums:
            if num in num_set:
                num_set.remove(num)
            else:
                num_set.add(num)
        return list(num_set)[0]

discussion을 보니 xor연산을 수행하는게 키 포인트였다.

xor연산의 특징을 살펴보면 다음과 같다.

• a xor 0 = a, a xor 0 = a (어떤 수와 0을 xor 연산하면 그 수가 그대로 나온다)
• a xor a = 0 (같은 수를 xor 연산하면 0이 나온다)
• a xor b xor a = a xor a xor b = 0 xor b = b (연산순서를 변경할 수 있다)

이를 이용해서 푼 풀이는 다음과 같다. 중복되는 수는 xor연산을 통해 0이 되었을 것이다.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res ^= num # xor 연산
        return res