Problem :

https://leetcode.com/problems/missing-number/


My Solution :

class Solution:
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ans = 0
for i, n in enumerate(nums, 1):
ans ^= i^n
return ans


Comment :

예전에 비슷한 문제를 풀었었는데, xor 연산의 아래 성질을 이용하면 된다.


n ^ n = 0

n ^ 0 = n


즉 위 방법대로 nums의 모든 원소들과 1~n까지 모든 숫자를 xor 연산시키면 한번만 등장하는 숫자가 남게 된다.


물론 정렬해서 O(nlogn)으로 푸는게 가장 손쉽게 접근하는 방법이다.