Single Number

problem

int 배열이 들어오면 단 하나의 중복되지않은 값을 찾는 문제입니다
[1,2,3,2,1] -> 3

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

solution

//problem no : 136
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int i=0, s=nums.size()-1;
        while(i < s){
            if(nums[i] != nums[i+1]){
                return nums[i];
            }
            i+=2;
        }
        return nums[s];
    }
};

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

후기

처음에는 정렬한 후에 비교하는 것으로 짠 후에 다른 사람들의 풀이를 보았는데,
밑에 코드가 있어서 당황했다.
xor 이 여기서 쓸 수 있다고? 라는 생각이 들었던것 같다

xor
00 - 0
10 - 1
01 - 1
11 - 0
인 비트연산자이다.

곰곰히 생각해보니까 xor에서 교환법칙이 성립하는 것이었다!

즉 [2,1,2,1,4] 같은 배열이
2^1^2^1^4
-> 2^2^1^1^4 가되어 중복된 값이 다 사라지고 single number만 남는 아름다운 코드가 되는 것이었다.