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

Single Number III

Master this topic with zero to advance depth.

Single Number III

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Medium

Examples

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Input: nums = [-1,0]
Output: [-1,0]
Approach 1

Level I: Brute Force (Frequency Map)

Intuition

The most intuitive approach is to use a hash map to count the frequency of each number and extract those with a count of 1.

⏱ $O(N)$💾 $O(N)$
java
class Solution {
    public int[] singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) map.put(n, map.getOrDefault(n, 0) + 1);
        int[] res = new int[2];
        int idx = 0;
        for (int n : map.keySet()) if (map.get(n) == 1) res[idx++] = n;
        return res;
    }
}
Approach 2

Level II: Sorting

Intuition

Sort the array to bring duplicates together. Iterate through the array; if current element is not equal to the next, it's a single number. Otherwise, skip two.

⏱ $O(N \log N)$💾 $O(1)$
java
class Solution {
    public int[] singleNumber(int[] nums) {
        Arrays.sort(nums);
        int[] res = new int[2];
        int idx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
            else res[idx++] = nums[i];
        }
        return res;
    }
}
Approach 3

Level III: Optimal (Bitwise Partitioning)

Intuition

XORing all numbers gives x⊕yx \oplus y. Find the lowest set bit in this XOR sum to divide all numbers into two groups (where this bit is set vs. not set). XORing within each group isolates xx and yy.

⏱ $O(N)$💾 $O(1)$
java
class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int n : nums) xor ^= n;
        int diffBit = xor & -xor;
        int[] res = new int[2];
        for (int n : nums) {
            if ((n & diffBit) == 0) res[0] ^= n;
            else res[1] ^= n;
        }
        return res;
    }
}
← Previous QuestionSingle Number II
Next Question →Bitwise AND of Numbers Range