# 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;
}
};