Single number

Given an array of nums of n integers. Every integer in the array appears twice except one integer. Find the number that appeared once in the array.

Brute Force: hashmap#

Build a frequency map by iterating through the array once, then iterate over the map to find the element whose count is exactly 1. This is correct and runs in O(n) time, but requires O(n/2) extra space to store approximately n/2 distinct keys — unnecessary given the elegant XOR solution below.

• note freq of all elements
• Iterate through hashmap, answer is the element with frequency 1

Time Complexity: O(n) + O(n/2)

Space Complexity: O(n/2)

Optimal Solution: XOR#

XOR has two key properties: a number XOR'd with itself is 0, and any number XOR'd with 0 is itself. By XOR-ing every element together, all pairs cancel out to 0, leaving only the single non-paired element. This works in a single pass with O(1) extra space — no hash map needed — making it the optimal solution for this problem.

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

        for(int i=0;i<nums.size();i++)
            xorR ^= nums[i];

        return xorR;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)