Single Number

Problem

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.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

1 <= nums.length <= 3 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4
Each element in the array appears twice except for one element which appears only once.

Solution

Approach 1: XOR Bit Manipulation

The key insight is that XOR has special properties:

a ^ a = 0
a ^ 0 = a
XOR is commutative and associative

Implementation

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

Approach 2: One-liner

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        from functools import reduce
        return reduce(lambda x, y: x ^ y, nums)

Approach 3: Using Hash Set (Not Optimal)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        seen = set()
        for num in nums:
            if num in seen:
                seen.remove(num)
            else:
                seen.add(num)
        return seen.pop()

Approach 4: Math Formula (Not Optimal)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 2 * sum(unique) - sum(all) = single number
        return 2 * sum(set(nums)) - sum(nums)

Complexity Analysis

XOR Approach:

Time Complexity: O(n), where n is the length of nums. Single pass through array.
Space Complexity: O(1), only using one variable.

Hash Set Approach:

Time Complexity: O(n)
Space Complexity: O(n) for the set.

Key Insights

XOR Properties: XOR of a number with itself is 0, and XOR with 0 is the number itself.
Cancellation: All paired numbers cancel out (num ^ num = 0), leaving only the single number.
Order Independence: XOR is commutative and associative, so order doesn’t matter.
Optimal Solution: XOR approach is optimal with O(1) space and O(n) time.
Mathematical Insight: For XOR: a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b
Single Pass: Only need to iterate through the array once.
No Extra Space: Unlike hash table approaches, XOR uses constant space.