AlgoMaster Logo

Single Number

Last Updated: March 20, 2026

easy
3 min read

Understanding the Problem

We have an array where every number shows up exactly twice, except for one number that appears only once. Our job is to find that unique number.

The straightforward part is finding which number doesn't have a pair. The tricky part is the constraint: we need O(n) time and O(1) space. That rules out sorting (O(n log n)) and hash maps (O(n) space). So we need something cleverer.

The key observation here is that this problem is fundamentally about pairing. Every number has a partner except one. If we could somehow cancel out all the pairs, we'd be left with the answer.

Key Constraints:

  • nums.length <= 3 * 10^4 → Even O(n^2) would be roughly 9 * 10^8 operations, which is borderline. O(n) is ideal.
  • -3 * 10^4 <= nums[i] <= 3 * 10^4 → Values can be negative, so index-based tricks won't work directly.
  • Every element appears exactly twice except one → This is the structural guarantee we can exploit.

Approach 1: Brute Force (Nested Loops)

Intuition

The most natural approach: for each element, check whether it has a duplicate somewhere else in the array. If no duplicate exists, that's our answer.

We pick each element one by one and scan the rest of the array looking for a match. If we finish scanning without finding one, we've found the single number.

Algorithm

  1. For each element nums[i], set a flag indicating no duplicate has been found.
  2. For each other element nums[j] where j != i, check if nums[i] == nums[j].
  3. If a match is found, mark that a duplicate exists and break the inner loop.
  4. If no match was found after the inner loop completes, return nums[i].

Example Walkthrough

1Initialize: check each element for a duplicate
0
4
1
1
2
2
3
1
4
2
1/3

Code

For every element, we're scanning the entire array to check for a duplicate. What if we could check whether we've seen an element before in O(1) time using a hash map?

Approach 2: Hash Map (Count Occurrences)

Intuition

Instead of rescanning the array for every element, we can count how many times each number appears using a hash map. Then we just find the number with a count of 1.

This trades space for time. A single pass to build the frequency map, another pass to find the element that appears once. Much better than nested loops.

Algorithm

  1. Create a hash map to store the count of each number.
  2. Iterate through the array. For each number, increment its count in the map.
  3. Iterate through the map and return the number whose count is 1.

Example Walkthrough

1Initialize: empty map = {}
0
4
1
1
2
2
3
1
4
2
1/7

Code

We're using O(n) extra space for the hash map, but the problem explicitly asks for O(1) space. Is there a way to "cancel out" paired elements without storing anything, leaving only the unpaired one?

Approach 3: XOR (Bit Manipulation)

Intuition

This is where bit manipulation shines. The XOR operator has three properties that make it perfect for this problem:

  1. Self-cancellation: a ^ a = 0 (any number XOR'd with itself becomes 0)
  2. Identity: a ^ 0 = a (any number XOR'd with 0 stays the same)
  3. Commutativity and Associativity: The order doesn't matter. a ^ b ^ a = a ^ a ^ b = 0 ^ b = b

So if we XOR all elements together, every pair cancels out to 0, and we're left with just the single number. It's like magic, except it's math.

Algorithm

  1. Initialize a variable result to 0.
  2. XOR every element in the array with result.
  3. After the loop, result holds the single number.

Example Walkthrough

1Initialize: result = 0
0
4
1
1
2
2
3
1
4
2
1/7

Code