Lintcode: Single Number

Given 2*n + 1 numbers, every numbers occurs twice except one, find it.

Have you met this question in a real interview? 

Yes

Example

Given [1,2,2,1,3,4,3], return 4

Challenge

One-pass, constant extra space.

Tags Expand 

Greedy

http://fisherlei.blogspot.com/2013/11/leetcode-single-number-solution.html
This problem requires Time: O(n) and Space O(1).
So both "sort then find" and "hashmap" don't work.

The key is to use ^(xor) bitwise operation: if same number xor twice, the initial number will not change(x ^ x = 0). Because 0 ^ x = x, so we set initial number 0.
0 ^ 0 = 0; 0 ^ 0 =0; 0^ 0 = 0;
0 ^ 1 = 1; 1 ^ 1 = 0; 0 ^ 1 = 1;

class Solution {
public:
 /**
  * @param A: Array of integers.
  * return: The single number.
  */
    int singleNumber(vector<int> &A) {
        // write your code here
        int res = 0;
        for(int i = 0; i < A.size(); i++){
            res = res ^ A[i];
        }
        return res;
    }
};