Single Number

Difficulty: Easy Source: NeetCode

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⁴
• -3 * 10⁴ <= nums[i] <= 3 * 10⁴
• Each element appears exactly twice, except for one element which appears exactly once.

Prerequisites

Before attempting this problem, you should be comfortable with:

• XOR (exclusive OR) — a bitwise operation where bits are 1 if they differ and 0 if they match
• Bit manipulation properties — specifically a ^ a = 0 and a ^ 0 = a

1. Brute Force

Intuition

The straightforward approach is to count how many times each number appears. Any number whose count is odd (specifically 1) is the answer. A hash map makes this easy: add each number as a key and track the frequency. One final pass to find the key with count 1 gives us the answer.

Algorithm

1. Create an empty hash map count.
2. For each number in nums, increment count[num] by 1.
3. For each key in count, return the key whose value equals 1.

Solution

def singleNumber(nums):
    count = {}
    for num in nums:
        count[num] = count.get(num, 0) + 1
    for num, freq in count.items():
        if freq == 1:
            return num


print(singleNumber([2, 2, 1]))        # 1
print(singleNumber([4, 1, 2, 1, 2]))  # 4
print(singleNumber([1]))              # 1

Complexity

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

2. XOR Bit Trick

Intuition

XOR has two magical properties that make this problem trivial:

• a ^ a = 0 — a number XORed with itself is always 0 (every bit cancels)
• a ^ 0 = a — a number XORed with 0 is itself

Because XOR is also commutative (a ^ b = b ^ a) and associative ((a ^ b) ^ c = a ^ (b ^ c)), the order doesn’t matter. When you XOR all numbers together, every pair of duplicates cancels to 0, and only the single number survives.

For [4, 1, 2, 1, 2]:

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4

In binary: 4 = 100, 1 = 001, 2 = 010. The pairs zero themselves out, leaving 100 = 4.

Algorithm

1. Initialize result = 0.
2. XOR every number in nums into result.
3. Return result.

Solution

def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result


print(singleNumber([2, 2, 1]))        # 1
print(singleNumber([4, 1, 2, 1, 2]))  # 4
print(singleNumber([1]))              # 1

Complexity

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

Common Pitfalls

Assuming sorted input. The XOR trick works regardless of order — no sorting needed. Don’t add a sort step unnecessarily.

Thinking XOR only works on positive integers. In Python, XOR works on negative integers too because they are represented in two’s complement. The trick is safe for the full input range.

Forgetting result must start at 0. 0 ^ a = a, so starting at 0 is the correct identity element for XOR accumulation. Starting at any other value will corrupt the result.