Difficulty: Easy · LeetCode 136

Problem

Every number in the array appears exactly twice except one. Find that single number. You must solve it in O(n) time and O(1) space.

Understanding the problem

XOR has two golden properties: x ^ x = 0 (pairs cancel) and x ^ 0 = x (identity). XOR-ing all elements causes every duplicate pair to vanish, leaving only the unique number.

Intuition

XOR all elements together. Paired numbers cancel to 0. The single unpaired number XOR'd with 0 returns itself.

Approach

Initialize answer = 0.
For each num in nums: answer ^= num.
Return answer.

Naive Solution — Brute Force

Use a hash set: add unseen numbers, remove them when seen a second time. Whatever remains is the answer.

Python

class Solution:
    def singleNumber(self, nums):
        seen = set()

        for num in nums:
            if num in seen:
                seen.remove(num)
            else:
                seen.add(num)

        return seen.pop()

C++

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_set<int> seen;

        for (int num : nums) {
            if (seen.count(num)) {
                seen.erase(num);
            } else {
                seen.insert(num);
            }
        }

        return *seen.begin();
    }
};

Java

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> seen = new HashSet<>();

        for (int num : nums) {
            if (seen.contains(num)) {
                seen.remove(num);
            } else {
                seen.add(num);
            }
        }

        return seen.iterator().next();
    }
}

JavaScript

var singleNumber = function(nums) {
    const seen = new Set();

    for (const num of nums) {
        if (seen.has(num)) {
            seen.delete(num);
        } else {
            seen.add(num);
        }
    }

    return seen.values().next().value;
};

Time: O(n) · Space: O(n)

Optimized Code (Python 3)

Python

class Solution:
    def singleNumber(self, nums):
        answer = 0

        for num in nums:
            answer ^= num

        return answer

C++

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int answer = 0;

        for (int num : nums) {
            answer ^= num;
        }

        return answer;
    }
};

Java

class Solution {
    public int singleNumber(int[] nums) {
        int answer = 0;

        for (int num : nums) {
            answer ^= num;
        }

        return answer;
    }
}

JavaScript

var singleNumber = function(nums) {
    let answer = 0;

    for (const num of nums) {
        answer ^= num;
    }

    return answer;
};

Time: O(n) · Space: O(1)

Takeaway

Pattern — Pairs + one unique → XOR all elements (x ^ x = 0, x ^ 0 = x)