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

view plainprint?

1. public class Solution {  
2.     public int singleNumber(int[] nums) {  
3.         Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();  
4.         for(int i = 0; i<nums.length; i++){  
5.               
6.             if(!map.containsKey(nums[i])){  
7.                 map.put(nums[i], false);  
8.             }else{  
9.                 map.put(nums[i], true);  
10.             }  
11.         }  
12.         for(int i: map.keySet()){  
13.             if (!map.get(i)) return i;  
14.         }  
15.         return 0;  
16.     }  
17. }  

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.

view plainprint?

1. public class Solution {  
2.     public int singleNumber(int[] nums) {  
3.         int result = 0;  
4.         for (int i = 0; i<nums.length; i++){  
5.               
6.             result ^= nums[i];  
7.         }  
8.         return result;  
9.     }  
10. }  

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