136. Single Number

문제

설명

정수형 배열 nums에서 유일한 수를 반환하면 된다.

풀이

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let uniqueNum = 0;
    
    for(let i = 0; i < nums.length; i++){
        uniqueNum ^= nums[i];
    }
    
    return uniqueNum;
};

XOR연산을 이용한 풀이이다. 조건에서
Each element in the array appears twice except for one element which appears only once. 각 요소는 한 번만 나타나는 요소를 제외하고 두 번 나타난다는 것을 알 수 있다.
1 ^ 1 = 0001(2) ^ 0001(2) = 0000(0) 같은 수를 두 번 xor 연산하면 0이 나오는 것을 이용해 고유한 수를 찾을 수 있다.

Example 1:
i: 0, unique: 0000(0) ^ 0010(2) = 0010(2)
i: 1, unique: 0010(2) ^ 0010(2) = 0000(0)
i: 2, unique: 0000(1) ^ 0001(1) = 0001(1)

// output: 1

----------------------------------------------------

Example 2:
i: 0, unique: 0000(0) ^ 0100(4) = 0100(4)
i: 1, unique: 0100(4) ^ 0001(1) = 0101(5)
i: 2, unique: 0101(5) ^ 0010(2) = 0111(7)
i: 3, unique: 0111(7) ^ 0001(1) = 0110(6)
i: 4, unique: 0110(6) ^ 0010(2) = 0100(4)

// output 4

위의 연산 과정을 보면 같은 수를 두 번 XOR 연산하게 되면 0으로 무산되는 것을 알 수 있다.