# 136. Single Number

Given a non-empty 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?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

# Solution

Approach 1: Hash table.

Approach 2: Math.

Approach 3: Bit manipulation -- a number XOR itself is 0. It's the best solution at O(1) space and O(N) time.

Approach 4: sort the nums then go through the array.

# Code (Python)

Approach 3:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

# Code (C++)

Approach 1:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_set<int> numsSet;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (numsSet.find(nums[i]) != numsSet.end())
                numsSet.erase(nums[i]);
            else
                numsSet.insert(nums[i]);
        }
        return *numsSet.begin(); // need *.
    }
};

Approach 2:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_set<int> numsSet;
        for (int i = 0; i < nums.size(); ++i)
        {
            numsSet.insert(nums[i]);
        }
        int setSum = std::accumulate(numsSet.begin(), numsSet.end(), 0);
        int numsSum = std::accumulate(nums.begin(), nums.end(), 0);
        return 2 * setSum - numsSum;
    }
};

Approach 3:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int singleNum = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            singleNum ^= nums[i];
        }
        return singleNum;
    }
};