Course4all

Single Number

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Bit Manipulation.

Single Number

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.
Easy

Examples

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

Level I: Brute Force (Frequency Map)

Intuition

Count the frequency of each number using a hash map. The number with frequency 1 is the answer.
⏱ $O(N)$💾 $O(N)$
java
class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums) map.put(x, map.getOrDefault(x, 0) + 1);
        for (int x : nums) if (map.get(x) == 1) return x;
        return -1;
    }
}
Approach 2

Level II: Sorting

Intuition

By sorting the array, identical elements become adjacent. We can then iterate through the array in steps of 2. If an element is not equal to its successor, it's the single number.
⏱ $O(N \log N)$💾 $O(1)$ (or $O(N)$ depending on sorting algorithm)
java
class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i += 2) {
            if (nums[i] != nums[i + 1]) return nums[i];
        }
        return nums[nums.length - 1];
    }
}
Approach 3

Level III: Optimal (XOR Manipulation)

Intuition

The XOR operator has two key properties: xoplusx=0x \\oplus x = 0 and xoplus0=xx \\oplus 0 = x. Since every number except one appears twice, XORing all elements together will cause the duplicates to cancel out, leaving only the single number.
⏱ $O(N)$💾 $O(1)$
java
class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int x : nums) res ^= x;
        return res;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionSwim in Rising Water
Next Question →Power of Two