[JavaScript] leetCode : Single Number

문제

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.

정수의 배열에서 동일하게 짝지어지지 않는 하나의 수를 찾아 반환하는 문제.

 

 

풀이

  let result = nums[0];

  for (let i = 1; i < nums.length; i++) {
    result = result ^ nums[i];
  }

  return result;

간단해보이면서도 묘하게 간단하지 않아서 결국 다른 코드를 보게 되었다 😇
논리 연산에서 XOR의 개념을 알고 있다면 무진장 간단하게 풀리는 문제였다.

 

지금까지 비트연산자는 별로 써본 적이 없었기에..
비트연산자 중 XOR 연산자(^)에 대해 간략하게 기록해본다.

우선 배타적 논리합인 XOR의 진리표는 다음과 같다.
같지 않을 때 참(1)을 반환한다.

 

이제 두 수를 비트로 따져서 뒤에서부터 같지 않으면 1, 같으면 0 으로 처리되는 식으로 계산이 되는.. 그런 식.

 

아래와 같은 테스트 케이스가 있을 때

[4,1,2,1,2]

 

다음과 같은 결과가 나오는 것을 볼 수 있다. 

위 결과를 풀어서 써보면,

1. 4와 1은 같지 않으니(참) 더한다.

2. (4+1)과 2는 같지 않으니(참) 더한다.

3. (4+1+2)와 1은 먼저 더해진 1과 겹치니(거짓) 뺀다.

4. (4+2)와 2는 먼저 더해진 2가 겹쳐니(거짓) 뺀다.

5. 4만 남는다.

 

이런 식으로 코드가 진행된다. 

 

위키백과를 보다보니 이런 식으로 짝수 홀수 패리티를 계산해서 오류 검출에 사용한다고 하고,

이런 방식으로 만들어진 패트리 트리도 있다고 한다. 흥미로운 사실 🤔