LeetCode 136 - Single Number

문제 살펴보기

숫자가 들어있는 배열이 주어진다. 이 배열에 있는 모든 숫자는 2개씩 들어있으며, 딱 한 숫자만 1개 들어있다.

1개만 있는 숫자를 찾아서 반환해야 한다. 

 

단, 숫자를 찾는 코드의 시간 복잡도는 0(n) (= linear runtime complexity) 이어야 하고,

공간 복잡도는 0(1) (=constant extra space) 이어야 한다.

---

생각의 흐름

단일 반복문과 비트 연산을 활용하면 주어진 요구사항을 지킬 수 있다...

 

비트 연산자 중 XOR을 사용하면 되고,  XOR의 규칙을 이용하면 된다.

x ^ 0 = x
x ^ y = 0

 

또한 XOR은 교환법칙이 성립한다. 따라서 다음과 같이 풀 수 있다.

x ^ y ^ x = x ^ x ^ y = y

 

---

풀어보기

int num = 0;
for (int n : nums) {
    num = num ^ n;
}
return num;

XOR 규칙을 꼭 기억해야겠다.