Blind 75 | Missing Number (Bit Manipulation 4 / 5)

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

Missing Number - LeetCode

 

Missing Number - 빠진 숫자

 

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.

 

0부터 n까지의 고유 숫자가 담긴 nums 배열이 있을때, 빠진 숫자를 찾아라.

 

 

 

풀이

 

1) 해쉬 맵을 사용하거나 

 

sum(3, 0, 1, 2) - sum(3, 0, 1) = 2인걸 이용해서 풀 수 있다.

 

 

2) 비트를 사용해서 푸는 방법은

 

[0, 1, 2, 3]이 있고 [0, 1, 3]이 있을 때

 

순서와는 상관없이 서로에게 ^를 했을때 나오는 결과는 빠진 숫자인 2가 되는데, 

이 점을 이용해서 풀 수 있다.

 

 

 

코드