137. Single Number II

https://leetcode.com/problems/single-number-ii/

---

세번씩 반복된 숫자들 사이에서, 한번만 나온 단 하나의 숫자 찾기

 

XOR의 성질을 알고 이를 적용해야 한다.

XOR의 성질은 다음과 같다.

 

function XOR([A, A]) // 0

function XOR([A, 0]) // A

function XOR([A, B, C, A, C]) // B

 

여기에 숫자를 대입해보면

 

function XOR([1, 2, 3, 1, 3,]) // 2

 

나랑 같은 착각을 할 수 있는 사람이 있어서 말해보자면, 배열을 순차적으로 탐색하면서 XOR한 값을 저장한다고 생각하지 말자.

 

let res;

 

res = 1 ^ 2;

res = 1 ^ 2 ^ 3;

res = 1 ^ 2 ^ 3 ^ 1;

 

위와 같이 '연산을 누적시킨다'고 생각해야지, 1^2의 결과값을 저장하고, 이 결과값을 가지고 3과 XOR하고, 이 결과값을 가지고 다시 1과 XOR하고... 하는 방식으로 생각하면 꼬인다. 이런 식으로 생각하지 않으면 아래 코드를 실행했을 때 3번이 반복 안된 숫자가 three 변수에 할당된 것에 의아함을 품고 이상한 방향으로 생각하게 될 수 있다.

 

var singleNumber = function (nums) {
    let ones = 0; // to collect bits that appear once
    let twos = 0; // to collect bits that appear twice
    let threes = 0; // to collect bits that appear three times

    for (let i = 0; i < nums.length; i++) {
        console.log(`i = ${i}, ` + `twos :` + twos + `, ` + `ones : ` + ones + `, ` + `threes : ` + threes);
        // twos is the union of itself and bits that just
        // appear the second time with the new number.
        twos = twos | (ones & nums[i]);
        ones = ones ^ nums[i];
        threes = ones & twos;

        // remove threes from ones and twos
        console.log(`i = ${i}, ` + `twos :` + twos + `, ` + `ones : ` + ones + `, ` + `threes : ` + threes);

        ones = ones & ~threes;
        twos = twos & ~threes;
    }

    return ones;
};

console.log(singleNumber([1, 1, 3, 1]));

 

https://leetcode.com/problems/single-number-ii/discuss/564646/Intuitive-Javascript-Solution

Intuitive Javascript Solution - LeetCode Discuss