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:
It's easy think out an O(n) space solution using Hash Map.
There is an idea originally comes from <Cracking the Coding Interview>: use XOR operator.
x XOR x = 0 and x XOR y XOR x = y.

public class Solution {
    public int singleNumber(int[] A) {
        for(int i = 1; i < A.length; i++)
            A[0] ^= A[i];
        return A[0];
    }
}

O(n) space solution:

public class Solution {
    public int singleNumber(int[] A) {
        HashMap hash = new HashMap();
        for(int i = 0; i < A.length; i++){
            if (!hash.containsKey(A[i])){
                hash.put(A[i], true);
            }
            else{
                hash.put(A[i], false);
            }
        }
        for(int i = 0; i < A.length; i++){
            if(hash.get(A[i]) == true){
                return A[i];
            }
        }
        return -1;
    }
}