LeedCode: Single World

Question:

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?

Analysis:

Since each number appears twice, if we use XOR for these numbers, the result will be 0. Then 0 XORs with the number only appears only once, the result will be that number. Since XOR is commutative, we can XOR all numbers and the result will be single number. 

This method can be used for an array where every element appears even times and one number appears odd times and we can find out that number with odd appearance. 

C++:

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

Cost:
O(n)