原题

LintCode 82. Single Number

Description

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

Example

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

Challenge

One-pass, constant extra space.

解题

利用异或的自反特性，a ^ b ^ b = a ^ 0 = a
所以成双的数都会异或两次0抵消，而单个的数则会异或一次0成为最终答案

class Solution {
public:
    /*
    * @param A: An integer array
    * @return: An integer
    */
    int singleNumber(vector<int> A) {
        // write your code here
        int x = 0;
        auto it = A.begin();
        while (it != A.end()) {
            x ^= *it++;
        }
        return x;
    }
};