LeetEye LeetEye
Easy Bit Manipulation ~5 min

Single Number

bit-manipulation 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.

Examples

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
Key Insight

XOR all numbers. Pairs cancel out (a ^ a = 0), leaving the single number.

XOR all numbers. Pairs cancel (a^a=0), single number remains (a^0=a). Commutative and associative.

How to Approach This Problem

Pattern Recognition: When you see keywords like single number bit-manipulation, think Bit Manipulation.

Step-by-Step Reasoning

1 What is a ^ a (XOR of number with itself)?
Answer: 0
XOR gives 1 only when bits differ. Same bits -> 0.
2 What is a ^ 0?
Answer: a
0 has no set bits. XOR with 0 preserves the original.
3 a ^ b ^ a equals:
Answer: b
a ^ b ^ a = a ^ a ^ b = 0 ^ b = b. Order doesn't matter.
4 XORing all elements works because:
Answer: Both A and B
Each pair XORs to 0. Only the single number survives.
5 This solution uses:
Answer: O(1) space
Only need one variable to accumulate XOR result.

Solution

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

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Bit Manipulation problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye