144.Single Number

EasyBit Manipulation · 1/7

Problem

Given a non-empty array of integers nums, every element appears exactly twice except for one element, which appears once. Find that single element.

You must implement a solution with linear runtime and constant extra space.

Examples

Input:  nums = [2, 2, 1]
Output: 1
Explanation: 2 appears twice, 1 appears once.

Input:  nums = [4, 1, 2, 1, 2]
Output: 4
Explanation: 1 and 2 each appear twice; 4 is the only unpaired value.

Input:  nums = [1]
Output: 1

Constraints

1 <= nums.length <= 3 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4
Each element appears twice except for one element which appears only once.

💡 Key Insight

XOR has three properties that solve this instantly: x ^ x = 0, x ^ 0 = x, and it is commutative and associative, so order does not matter. XOR-ing the whole array makes every pair cancel to 0, leaving only the single number — in one pass with one variable.

Brute Force

TimeO(n²)SpaceO(1).

Intuition

For each element, count how many times it appears in the array. The one with count 1 is the answer.

Algorithm

For each index i:
- Count occurrences of nums[i] by scanning the whole array.
- If the count is 1, return nums[i].
(Unreachable for valid input) return -1.

Visualization

nums = [4, 1, 2, 1, 2]
nums[0] = 4 → appears 1 time → return 4

Code

java

class Solution {
    public int singleNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] == nums[i]) {
                    count++;
                }
            }
            if (count == 1) {
                return nums[i]; // the unpaired element
            }
        }
        return -1; // not reached for valid input
    }
}

Complexity

Time: O(n²) — a full scan for every element.
Space: O(1).

Hash Set

TimeO(n)SpaceO(n)

Intuition

Walk the array with a set. The first time we see a value we add it; the second time we remove it. Pairs cancel out, so at the end the set contains only the single number.

Algorithm

Create an empty HashSet<Integer> seen.
For each num: if seen contains it, remove it; otherwise add it.
Return the only element left in seen.

Visualization

nums = [4, 1, 2, 1, 2]
4 → {4}
1 → {4, 1}
2 → {4, 1, 2}
1 → {4, 2}       (removed)
2 → {4}          (removed)
answer = 4

Code

java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            // remove() returns true if num was present: its pair has been found
            if (!seen.remove(num)) {
                seen.add(num);
            }
        }
        return seen.iterator().next(); // only the single number remains
    }
}

Complexity

Time: O(n) — one O(1) average set operation per element.
Space: O(n) — up to about n / 2 values are in the set at once.

Bit Manipulation with XOROptimal

TimeO(n)SpaceO(1)

Intuition

XOR every number into an accumulator starting at 0. Since XOR is order-independent, we can imagine regrouping the pairs together: (a ^ a) ^ (b ^ b) ^ ... ^ single = 0 ^ 0 ^ ... ^ single = single. Bit-wise, every bit position flips an even number of times for paired values, so only the single number's bits survive.

Algorithm

result = 0.
For each num, result ^= num.
Return result.

Dry Run

flowchart LR
    A["result = 0 (000)"] -->|"^ 4 (100)"| B["result = 100"]
    B -->|"^ 1 (001)"| C["result = 101"]
    C -->|"^ 2 (010)"| D["result = 111"]
    D -->|"^ 1 (001)"| E["result = 110"]
    E -->|"^ 2 (010)"| F["result = 100 = 4"]

Code

java

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

Complexity

Time: O(n) — one pass.
Space: O(1) — a single integer.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(1)
Hash Set	O(n)	O(n)
XOR	O(n)	O(1)

Common Pitfalls

Starting the accumulator at something other than 0 — 0 is XOR's identity; any other seed corrupts the result.
Worrying about negative numbers — XOR works on the two's-complement bits, so negatives cancel just like positives.
Using a sum trick like 2 * sum(set) - sum(nums) — correct, but it needs O(n) space and can overflow in other variants.
Applying the XOR trick to Single Number II (every other element appears three times) — pairs no longer cancel; that variant needs per-bit counting mod 3.