Problem
Problem ID: 136
Title: Single Number
Difficulty: Easy
Description:
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Thoughts
Solving this problem with linear space is easy but to do it in constant space is tricky. Using XOR technique to remove identical numbers is a good technique
Solution
General Idea
As k ^ k = 0
, we will just need to continuously XOR across all numbers.
Implementation
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for (auto num : nums) ret ^= num;
return ret;
}
};