Leetcode :: Missing Number

Problem

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Guess

• 빠진 수를 찾기만 하면 된다라.. 딕셔너리를 이용하면 순식간에 풀겠지만
• Follow up 항목을 따라가려면 조금 발상의 전환이 필요하다. (딕셔너리는 공간복잡도 O(n))
• 상수 공간으로 해결할 방법이 도저히 떠오르지 않았는데, XOR을 이용한 유니크한 솔루션을 발견했다.

1 ^ 1 = 0
0 ^ 0 = 0
0 ^ 1 = 1

XOR은 이처럼 서로 같으면 0, 다르면 1을 부여하는 비트연산이다.
중요한 특성은, 0과 a가 XOR하면 무조건 a가 나오게 되어있다.

즉, 범위 [0...n] 의 모든 요소와 XOR을 하면, 서로 다른 수 일 때 무조건 0이 아닌 수가 나온다! -> 사라진 수가 된다.

Solution

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        missing = len(nums)
        for i,num in enumerate(nums):
            missing ^= i ^ num
        return missing