leetcode 260. Single Number III C++

문제 :

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice.

Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

class Solution {
public:
    vector<int> singleNumber(vector<int>& A) {
        int x = 0;
        for (int n : A) x ^= n;
        int lb = x & -(unsigned)x, a = 0;
        for (int n : A) {
            if (n & lb) a ^= n;
        }
        return {a, x ^ a};
    }
};

문제는 간단하지만 해답은 쉽지 않았다.

 

비트마스크를 사용하여 푸는데, 코드를 해석하기 이전에 개념 두가지를 짚고 넘어가야한다.

1. 0에 대하여 같은 수를 XOR 두 번 하면 0이된다.
2. 어떤 비트가 있을  때 가장 낮은 자리의 1을 구하는 식은 x ^ (x & (x - 1)) 이다.

위 두 개념을 이용하여 아래와 같이 풀게된다.

먼저 구하려는 두 수를 a,b 라고 하자.

1. 0에 대하여 주어진 모든 수를 XOR 연산 하는 것은, 곧 우리가 구하려는 중복이 없는 수 a XOR b 연산값과 같다. (XOR 연산은 교환법칙이 성립되므로 중복된 수는 결국 0이 된다.) 이 값을 x라고 하자.
2. x의 어떤 비트가 1이라는 의미는 그 비트 자리에서 a,b 두 수의 비트가 다르다는 의미이다. 즉, a가 그 비트 자리에서 1이라면 b는 0이라는 뜻이다.
3. x의 가장 낮은 자리의 1의 위치를 구한다. (위의 2번 개념을 이용해서)
4. 3번에서 구한 수와 AND 연산을 했을 때 0이 아닌 수(즉, 이 비트 자리에서 1인 수)에 대하여, 0에 대하여 모두 XOR 연산한다.
5. 4번의 결과로 결국 어떤 수 a만 남게된다. (1번 개념)
6. a XOR b = x 였으므로, a XOR x = b이다.
7. 따라서 답은 (a, a XOR x)

 

참고

- https://github.com/lzl124631x/LeetCode/tree/master/leetcode/260.%20Single%20Number%20III