What is the brute force approach and complexity for Single Number?

For each value, scan the array and count it; return the one with count 1 with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Single Number?

XOR every number into one running value; the pairs cancel and the single one is left with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Single Number?

Look for key signals in the prompt: "every element appears twice except one" indicates Values come in pairs, so pairs must cancel out. That is what XOR does.; "linear time, constant extra space" indicates No hash map and no sorting. Read the array once, with one running value.; "find the one that appears once" indicates The answer is whatever is left after every pair has cancelled..

Single Number

Easy·LeetCode #136Basic Anchor

LeetCode

Jump:

30-Second Mental ModelXOR cancellation (single number)

Complexity:O(N²)→O(N)

Key Insight

Start with ans = 0 and XOR every number into it. Two equal numbers cancel, because x ^ x = 0. Zero changes nothing, because x ^ 0 = x, so the single value stays. The order does not matter, so the pairs do not need to sit next to each other.

Core Validity Invariant

The running value is valid when it equals the XOR of every number read so far. At the end, every repeated value has appeared twice and cancelled, so only the single value is left. Pairs cancel out, whatever the order.

Problem

You get an array nums. Every value in it appears twice, except for one value that appears only once. Return that single value.

The numbers are in no particular order. Your solution must run in linear time and use constant extra space.

Input

An integer array nums with at least one value. Every value appears twice except one.

Output

The one value that appears exactly once.

Example 1

Input: nums = [2, 2, 1]

Output: 1

The 2 shows up twice, so the value with no partner is 1.

Example 2

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

Output: 4

1 and 2 each show up twice. The 4 is the only value without a partner.

Example 3

Input: nums = [1]

Output: 1

There is only one value, so it is the single one.

Constraints

• 1 ≤ nums.length ≤ 3 · 10^4
• −3 · 10^4 ≤ nums[i] ≤ 3 · 10^4
• Every value appears twice, except one value that appears once.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I counted how many times each value appears, which count would I be looking for?
2.
Can I answer with a simple yes/no check, like 'is this value in the array?' Why or why not?
3.
What does XOR give when I combine a number with itself? And with 0?
4.
If I XOR every number in the array together, which numbers should disappear?
5.
Does the order of the numbers change the result of a chain of XORs?

Brute force approach

Idea

For each value in nums, scan the whole array and count how many times it appears. The first value whose count is exactly 1 is the answer.

Thinking process

1
The question asks for the value that shows up once. So for each value, count how many times it shows up.
2
On [4, 1, 2, 1, 2], the count of 4 is 1, so 4 is the answer. Checking 1 first gives a count of 2, so it is skipped.
3
Each count needs a full scan of the array, and we may need to count every value. That is a scan for each value.

Code & Implementation

brute.cpp

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int n = nums.size();
        // For each value, scan the whole array and count how many times it shows up.
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (nums[j] == nums[i]) count++;
            }
            if (count == 1) return nums[i];
        }
        return -1;   // never reached: exactly one value appears once
    }
};

Complexity

Time O(N²)Space O(1)

Each of the n values needs a full scan of n numbers, so there are about n · n comparisons. With n = 3 · 10^4, that is about 9 · 10^8 comparisons, which is too slow for a fast judge.

Better approach

Why brute force is slow

Every count rescans the whole array, so the same numbers are read again and again.

What repeated work are we doing?

Counting 4 reads all five numbers, and counting 1 reads all five numbers again. Each value is re-read once per candidate.

What information can we reuse?

One pass fills a map of counts. After that, each count is a lookup, not a rescan.

New approach

Idea

Walk the array once and store each value's count in a hash map. Then look through the map for the value whose count is 1.

Thinking process

1
The brute force re-reads the whole array for every value. Most of that work is repeated.
2
Instead, walk the array once and add 1 to count[x] for each x. On [4, 1, 2, 1, 2] the map becomes {4: 1, 1: 2, 2: 2}.
3
Then pick the key whose count is 1. Here that is 4.

Code & Implementation

better.cpp

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // One pass: count how many times each value appears.
        unordered_map<int, int> count;
        for (int x : nums) count[x]++;

        // Return the value whose count is 1.
        for (auto& [value, c] : count) {
            if (c == 1) return value;
        }
        return -1;   // never reached
    }
};

Complexity

Time O(N)Space O(N)

One pass to count and one pass over the map. The map can hold up to about n entries, so this uses extra memory that grows with the input. The follow-up asks for O(1) space.

Optimized approach

Idea

Start from brute force

The brute force counts each value by rescanning the array. The better version counts every value once, but it stores a count for each value. The optimal version does not count at all: it lets equal pairs cancel as they arrive.

Find the repeated work

Counting needs memory, because you must remember how many times each value was seen. XOR is a shortcut: a pair of equal values leaves nothing behind in the running value, so nothing has to be stored.

Define the state — what variables do I need?

ans: The XOR of every number read so far. A value seen twice leaves no trace; a value seen once is still in it.
x: The number being read from nums right now. It is not stored anywhere else.

Define validity

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

ans = 0

0 does nothing in XOR (x ^ 0 = x), so it is a safe starting point.

For every x in nums

ans ^= x

If x is the second copy of a value, it cancels the first copy (x ^ x = 0). If x is the single value, nothing cancels it, so it stays in ans.

After the loop

return ans

Every repeated value has cancelled, so only the single value is left.

What does the current window add to the answer?

Each number either adds itself to ans (its first copy) or removes itself (its second copy). After the loop, ans holds the XOR of the values that appear an odd number of times. Here that is only the single value.

Code & Implementation

optimal.cpp

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // Start at 0: 0 ^ x = x, so the start adds nothing.
        int ans = 0;
        // Each value that appears twice XORs to 0 and disappears, in any order.
        for (int x : nums) ans ^= x;
        return ans;
    }
};

Complexity

Time O(N)Space O(1)

One pass with a single running value. Equal numbers cancel as they come in, so no map or extra array is needed.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each value, scan the array and count it; return the one with count 1	O(N²)	O(1)
Better	Count every value once in a hash map, then return the value with count 1	O(N)	O(N)
Optimal	XOR every number into one running value; the pairs cancel and the single one is left	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“every element appears twice except one”Values come in pairs, so pairs must cancel out. That is what XOR does.
“linear time, constant extra space”No hash map and no sorting. Read the array once, with one running value.
“find the one that appears once”The answer is whatever is left after every pair has cancelled.

Pairs of equal values+XOR of a pair → 0+XOR of everything → the single value→XOR cancellation (single number)

This is the anchor for the XOR sub-pattern. XOR works because a pair cancels itself and 0 is the neutral value. The next questions change the setup. Decode XORed Array uses XOR to undo one step. Single Number III has two singles, so one XOR total mixes them together. Single Number II has triples, which XOR does not cancel.

Don't make this mistake

Using the XOR-all trick when the others appear three times

✗ int ans = 0; for (int x : nums) ans ^= x; // on [2, 2, 3, 2]

✓ Count the 1s in each bit position, then keep count % 3 (see Single Number II).

This is the pattern-confusion trap. On [2, 2, 3, 2] the XOR is 2 ^ 2 ^ 3 ^ 2 = 1, but the answer is 3. The first two 2s cancel, leaving 3, and the third 2 XORs it to 1. Three equal values do not cancel: x ^ x ^ x = x.

Starting the running value at nums[0] or at 1

✗ int ans = nums[0]; for (int x : nums) ans ^= x;

✓ int ans = 0; for (int x : nums) ans ^= x;

nums[0] gets XORed in twice, once as the start and once in the loop, so it cancels itself. On [4, 1, 2, 1, 2] this gives 4 ^ 4 ^ 1 ^ 2 ^ 1 ^ 2 = 0, not 4. Starting at 1 is also wrong: it adds a 1 to the result (1 ^ 4 = 5). The neutral start is 0.

Comparing neighbours (this needs a sorted array)

✗ for (int i = 0; i + 1 < n; i += 2) if (nums[i] != nums[i + 1]) return nums[i];

✓ int ans = 0; for (int x : nums) ans ^= x; return ans;

This only works if equal values sit next to each other, which needs a sort first (O(N log N)). On [1, 2, 1, 2, 4] the first two numbers differ, so it returns 1. The answer is 4.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Bit Manipulation translate into production architectures and low-level memory mechanics.

LLD Architecture