[Dart] 136. Single Number

1. 문제

https://leetcode.com/problems/single-number/description/?envType=study-plan-v2&envId=leetcode-75

 

 

 

2. 문제 요구사항

1) 정수 배열 nums가 주어진다.

2) 모든 숫자는 두 번식 등장하며, 단 하나만 예외이다.

3) 이 유일한 숫자를 찾는다.

 

 

3. 핵심 아이디어

1) XOR 연산

XOR 연산은 같으면 0, 다르면 1을 반환하는 이진 연산이다.

 

A	B	A ^ B
0	0	0
1	1	0
0	1	1
1	0	1

 

 

여기서 중요한 특징은 다음과 같다.

- 자기 자신과 XOR 하면 0이다.

A ^ A = 0

4 ^ 4 = 0100 ^ 0100 = 0000 = 0

 

- 0과 XOR 하면 자기 자신이다.

A ^ 0 = A

4 ^ 0 = 0100 ^ 0000 = 0100 = 4

 

- 자기 자신과 자기 자신을 XOR 하면 0이 된다.

A ^ A = 0

4  ^ 4 = 0100 ^ 0100 = 0000

 

 

2) 코드

class Solution {
  int singleNumber(List<int> nums) {
    int result = 0;
    for(int num in nums) {
      result ^= num;
    }
  
    return result;
  }
}

 

시간 복잡도 : O(n)

 

공간 복잡도 : O(1)