[LeetCode][Python3] 268. Missing Number

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)으로 푸는게 가장 손쉽게 접근하는 방법이다.