LeetCode 136 - Single Number (Easy)

문제

LeetCode - 104번

풀이 과정

하나의 숫자만 1개가 존재하고 나머지 숫자들은 2개씩 존재하는 배열에서
1개 존재하는 숫자를 single number 라고 했을 때 해당 수를 찾는 문제입니다.

문제 조건에서 O(N) 에 추가 메모리 공간을 사용하지 않고 구현하는 방법을 찾아야합니다.

이를 위해서 비트 연산자 중에서 xor 를 활용하도록 합니다.
xor 연산은 서로 다른 비트에서만 1이고 나머지는 0이기 때문에 같은 숫자끼리 xor 을 하면 0이 됩니다.

따라서 single number 를 제외한 모든 수는 2개씩 존재하기 때문에 xor 결과 0이 되고
0 ^ single number = single number 로 구할 수 있습니다.

코드

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  const answer = nums.reduce((acc, num) => acc ^ num);
  return answer;
};