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

Single Number II

Master this topic with zero to advance depth.

Single Number II

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

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

Medium

Examples

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

Level I: Brute Force (Frequency Map)

Intuition

The simplest way to track occurrences is using a hash map or frequency array. We count how many times each number appears and return the one with a count of 1.

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

Level II: Sorting

Intuition

If we sort the numbers, identical numbers will be adjacent. We can jump in steps of 3 and check if nums[i] is different from nums[i+1].

⏱ $O(N \log N)$💾 $O(1)$ (or $O(N)$ depending on sort implementation)
java
class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i += 3) {
            if (nums[i] != nums[i + 1]) return nums[i];
        }
        return nums[nums.length - 1];
    }
}
Approach 3

Level III: Optimal (Bit Manipulation)

Intuition

Every number that appears three times will contribute exactly 3 (or 0) to the sum of bits at any given position. If we sum the bits at each position i∈[0,31]i \in [0, 31] and take modulo 3, the remaining bit belongs to the single number.

⏱ $O(N)$💾 $O(1)$
java
class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int x : nums) if (((x >> i) & 1) == 1) sum++;
            if (sum % 3 != 0) res |= (1 << i);
        }
        return res;
    }
}
← Previous QuestionPower of Two
Next Question →Single Number III