Course4all
Join us on telegram
Home/dsa/Bit Manipulation/Single Number

Single Number

Master this topic with zero to advance depth.

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;
    }
}
← Previous QuestionSwim in Rising Water
Next Question →Power of Two