Course4all

Single Number II

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Bit Manipulation.

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;
    }
}

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 QuestionPower of Two
Next Question →Single Number III