Single Number

Problem Description

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?

Solutions
I. Using Hash Table
We can solve this problem by simply counting the number of times a number appeared.
Java Code

public class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        for(int i = 0; i<nums.length; i++){
            
            if(!map.containsKey(nums[i])){
                map.put(nums[i], false);
            }else{
                map.put(nums[i], true);
            }
        }
        for(int i: map.keySet()){
            if (!map.get(i)) return i;
        }
        return 0;
    }
}

II. Bit manipulation
In this solution, we have the following observation, given an integer N:
0 ^ N = N
N ^ N = 0
Where ^ is the XOR operator.

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