[LeetCode] 136. Single Number

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?

Thought process:

Iterate through the array. Maintain a set of integers seen so far. If a number is already in the set, erase it from the set. In the end the set will have one element remaining, which is the single number.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public: int singleNumber(vector<int>& nums) { unordered_set< int > set; for (int num : nums) { if (!set.insert(num).second) { set.erase(num); } } return *set.begin(); } };

Time complexity: O(n). Space complexity: O(n).


Follow-up:
This problem can be solved without using extra space using the XOR operation. A XOR A = 0. By XORing every number in the array, the equal bits of two numbers will be erased, whereas the different bits will remain. So after the iterations, whatever remians is the single number. Note that "xor" is a keyword in C++, so don't use that as the variable name.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12

class Solution { public: int singleNumber(vector<int>& nums) { int x = 0; for (int num : nums) { x ^= num; } return x; } };

Time complexity: O(n). Space complexity: O(1).