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?

Solution : 

Rule of thumb :  XORing a number with itself results in 0. 

eg: A = [2, 3, 3, 1, 1]

if we XOR the numbers we will be left with the number that only occurred once.

0010 ^ 0011 ^ 0011 ^ 0001 ^ 0001  = 0010 = 2.

Code : 

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

};

Hope that helped!