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: Bit Manipulator

If we take XOR of zero and some bit, it will return that bit

* a XOR 0 = a

If we take XOR of two same bits, it will return 0

* a XOR a = 0

a XOR b XOR a = (a XOR a) XOR b = 0 XOR b = b

So we can XOR all bits together to find the unique number.

    int singleNumber(int A[], int n) {
        int result = 0;
        for(int i=0; i<n; i++) {
            result ^= A[i];
        }

        return result;
    }