Single Number

EasyBit Manipulation · XOR🧩 Bit Manipulation LeetCode #136 ↗Updated Oct 30, 2026

Problem

In a non-empty integer array nums, every value occurs exactly twice except one value that occurs once. Return that lonely value, ideally in linear time with constant extra memory.

Input[2,2,1]Output1

Input[4,1,2,1,2]Output4

Input[1]Output1

1 ≤ n ≤ 3·10⁴ · -3·10⁴ ≤ nums[i] ≤ 3·10⁴ · Required: O(n) time, O(1) extra space.

Try it yourself

Java

class Solution {
    public int singleNumber(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

XOR is a cancel-out operator: x ^ x = 0, x ^ 0 = x, and order doesn't matter. XOR everything and all pairs vanish, leaving the single value.

PatternBit Manipulation

Instinct Pairs that cancel, counting 1s, powers of two, subsets as numbers, or 'no + or - allowed' - drop to binary and use XOR, AND, OR and shifts.

Memory hack XOR is a forgetful twin detector - see something twice and it vanishes; n & (n-1) snips off the last lit bulb.

Open the Bit Manipulation guide →

Approaches

Brute ForceCheck Every Element Against All

Time O(n²)Space O(1)

For each index i, scan the whole array for another index with the same value. The first element with no partner is the answer.

Java

public int singleNumber(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        boolean isSingle = true;
        for (int j = 0; j < nums.length; j++) {
            if (i != j && nums[i] == nums[j]) {
                isSingle = false; // found its pair
                break;
            }
        }
        if (isSingle) return nums[i];
    }
    return -1; // unreachable for valid input
}

No extra memory, but quadratic — too slow for n = 3·10⁴ in the worst case.

BetterHash Map Frequency Count

Time O(n)Space O(n)

Count occurrences of each value in a HashMap, then return the key whose count is 1. Hash lookups are O(1) on average, so it is linear.

Java

public int singleNumber(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int num : nums) {
        count.put(num, count.getOrDefault(num, 0) + 1);
    }
    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
        if (e.getValue() == 1) return e.getKey();
    }
    return -1; // unreachable for valid input
}

Linear time and generalises to any counts, but uses O(n) memory.

OptimalXOR All Elements

Time O(n)Space O(1)

XOR is commutative and associative, so a^b^a regroups to (a^a)^b = 0^b = b. Folding the whole array with ^ cancels every duplicated value bit by bit, leaving only the single number.

Java

public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num; // pairs cancel to 0
    }
    return result;
}

Dry run[4,1,2,1,2]

i index changed

i=0
4
i
1

2

1

2

0^4 = 4 (100)
i=1
4

1
i
2

1

2

4^1 = 5 (101)
i=2
4

1

2
i
1

2

5^2 = 7 (111)
i=3
4

1

2

1
i
2

7^1 = 6 (110)
i=4
4

1

2

1

2
i
6^2 = 4 ✔

One pass, one integer of state — meets both requirements.

Pro tip

One-liner: Arrays.stream(nums).reduce(0, (a, b) -> a ^ b).

At a glance

Level	Approach	Time	Space
Brute Force	Check Every Element Against All	`O(n²)`	`O(1)`
Better	Hash Map Frequency Count	`O(n)`	`O(n)`
Optimal	XOR All Elements	`O(n)`	`O(1)`

Common pitfalls

Using sum tricks (2·sum(set) - sum) — needs O(n) space and can overflow.
Starting the XOR accumulator at anything other than 0.
Assuming non-negative values — XOR works fine on negatives (two’s complement).

Interview tips

State the three XOR laws out loud: self-inverse, identity 0, commutative.
Mention sorting (O(n log n), O(1)) as a middle ground if asked.
Expect follow-ups: Single Number II (thrice) and III (two singles).

Pattern

XOR cancellation → find the odd-one-out when everything else appears an even number of times.

My notes saved in this browser