single-number XOR

gistfile1.txt

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

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?


/*
솔직히 이건.. 알고리즘적 사고 테스트라기보단, XOR을 이용한 trick에 가깝다.
예전에 메모리가 진짜 부족할때 XOR을 이용한 코딩을 종종했다고함.(swap)
*/

class Solution {
public:
    int singleNumber(int A[], int n) {
        int res = 0;
         
        for(int i=0; i<n ; i++) {
            res ^= A[i];
        }
        
        return res;
    }
};