Single Number

How it works

We are given an array where every number appears exactly twice except one, and we need to find that unique number.

This problem is a perfect fit for bit manipulation, specifically the XOR (^) operation.

Key properties of XOR:

• a ^ a = 0 (a number XORed with itself cancels out)
• a ^ 0 = a (XOR with 0 keeps the number unchanged)
• XOR is commutative and associative, so order does not matter

Because of these properties:

• all numbers that appear twice will cancel each other out
• the number that appears once will remain

Steps

1. Initialize res = 0.
2. Iterate through each number in the array:
   • update res = res ^ num
3. After processing all numbers:
   • res contains the single number
4. Return res.

Complexity

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

Things to watch for

Not Knowing XOR Properties

The optimal solution relies on understanding that a ^ a = 0 and a ^ 0 = a. Candidates unfamiliar with bitwise operations often resort to hash sets or sorting, missing the elegant O(1) space solution. Memorizing these XOR properties is essential for bit manipulation problems.

Using Extra Space Unnecessarily

A common mistake is implementing a hash map or set to track occurrences when the problem explicitly asks for O(1) extra space. While these approaches work functionally, they fail to meet the space constraint and miss the intended learning objective of the problem.

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res = num ^ res
        return res

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