# Single Number
###### tags: `coding interview`
## Problems
https://leetcode.com/problems/single-number/
## Solution
### Hash

class Solution {
   public:
    int singleNumber(vector<int>& nums) {
        // use an dictionary to implement
        unordered_map<int, int> table;

        for (auto iter = nums.begin(); iter != nums.end(); iter++) {
            if (table.find((*iter)) == table.end()) {
                table.insert(*iter);
            } else {
                table[*iter] += 1;
            }
        }

        for (auto iter = table.begin(); iter != table.end(); iter++) {
            if (iter->second == 1) {
                return iter->first;
            }
        }

        return 30001;
    }
};

### Bit Manipulation

class Solution {
   public:
    int singleNumber(vector<int>& nums) {
        // use an dictionary to implement
        int ans = 0;
        
        for (vector<int>::const_iterator iter = nums.begin(); iter != nums.end(); iter++) {
            ans = ans ^ *iter;
        }
        
        return ans;
    }
};

## Analysis
* Time Complexity: $O(n)$
* Space Complexity: $O(n)$, for hash $O(1)$ for bit manipulation

## Test Case
* normal

[1, 2, 2, 3]

* extreme

[-30000, 30000, -30000, 30000, ....] continue the pattern