Problem

Problem: https://leetcode.com/problems/single-number/

Approach

하나만 다른 걸 알아내는 법이 뭐지? -> 같은 걸 없애버리는 법이 뭐지?

Simple Explanation

비트 연산 XOR 을 이용한다!

1^1=0
1^0=1
0^1=1
0^0=0

같은 것을 XOR 하면 0, 서로 다른 것을 XOR 하면 1이 된다

위 문제에서는 모든 element가 2번씩 나오고 하나의 element만 1번 등장하므로
모든 element들을 XOR 해버리면 2번씩 나온 녀석들은 0이 될테고, 하나의 element만 남게 됨

Code

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = nums[0];        
        if (nums.size() == 1) return result;
        
        for (int i = 1; i < nums.size(); i++) {
            result = result ^ nums[i];
        }
        
        return result;
    }
};

Complexity

1) Time

2) Space