[JS] Single Number

🔒 문제 (LeetCode 136)

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Constraints:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

 

🌊 입출력

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

 

---

 

🔑 해결

🌌 알고리즘 - 비트 조작

A와 B에 대한 XOR 연산의 결과는 아래와 같다

A	B	Y
0	0	0
0	1	1
1	0	1
1	1	0

1. A^A=0
2. A^B^A=B
3. (A^A^B) = (B^A^A) = (A^B^A) = B
4. a^a^a......... (even times)=0 and a^a^a........(odd times)=a

이와 같은 성질을 이용하여 nums의 모든 요소에 대해 XOR 연산을 계속한다면 그 결과로 중복이 없는 수를 반환하게 된다.

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    // XOR 연산 - 같을 때만 0
    return nums.reduce((prev, cur) => prev ^ cur);
};