[leetcode_136]Single Number

Given an array where every element appears twice except for one, find that single element without using extra memory.

This problem can be solved using XOR, which requires no extra memory.

Accepted on the first try. Here is the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int singleNumber(int A[], int n) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int ans = A[0];
        for(int i = 1; i < n; i++)
        {
            ans = ans ^ A[i];
        }
        return ans;
    }
};