ProblemPermalink

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.

ThoughtsPermalink

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

SolutionPermalink

General Idea

As k ^ k = 0, we will just need to continuously XOR across all numbers.

ImplementationPermalink

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