Single Number II - Solution & Explanation
Problem Statement
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.
Example 1:
Input: nums = [2,2,3,2] Output: 3
Example 2:
Input: nums = [0,1,0,1,0,1,99] Output: 99
Constraints:
1 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1- Each element in
numsappears exactly three times except for one element which appears once.
Approach Overview
Problem Overview: You are given an integer array where every element appears exactly three times except for one element that appears once. The task is to find that single element. The challenge is doing it efficiently without extra memory while scanning the array only once.
Approach 1: Use a Map to Count Frequencies (O(n) time, O(n) space)
The straightforward solution counts how many times each number appears. Iterate through the array and store frequencies in a hash map using map[num]++. After building the frequency table, iterate through the map and return the number whose count equals 1. Hash lookups and insertions run in constant time on average, so the entire pass over the array costs O(n) time.
This method is easy to implement and works for any frequency-based variant of the problem. The downside is memory usage: the map may store up to n distinct elements, giving O(n) space complexity. In interviews, this approach demonstrates that you recognize the frequency pattern but it doesn't fully exploit the bit constraints of the problem. Problems involving counting or frequency tables commonly appear in array and hash-based questions.
Approach 2: Bit Manipulation (O(n) time, O(1) space)
The optimal approach analyzes the binary representation of every number. Since all numbers except one appear exactly three times, the sum of bits at each position must be a multiple of three for those repeated numbers. The unique number contributes the remaining bits. For each bit position from 0 to 31, iterate through the array and count how many numbers have that bit set.
Compute count % 3 for each bit position. If the remainder is 1, the unique number has that bit set. Reconstruct the answer by setting those bits in the result integer. This works because triples cancel out under modulo 3 arithmetic. The algorithm scans the array for each bit position, giving O(32 * n) time which simplifies to O(n). Only a few integer variables are used, so space complexity is O(1).
This technique is a classic example of counting bits with modular arithmetic and appears frequently in bit manipulation interview questions. It avoids auxiliary data structures and works even when the input size is large.
Recommended for interviews: The bit manipulation approach is the expected optimal solution. Interviewers want to see whether you recognize the pattern that repeated numbers cancel out when counted modulo three. Starting with the hash map solution shows clear thinking, but transitioning to the constant-space bit technique demonstrates stronger algorithmic skill and familiarity with low-level operations.
Approach 1: Bit Manipulation
This approach uses bit manipulation to solve the problem with constant space and linear runtime. The idea is to count the number of times each bit is set in the given numbers modulo 3 using two integers. This effectively filters out the bits that appear in numbers repeated thrice and leaves the bits of the unique number.
In this code, we maintain two variables ones and twos to track the bits' appearances. When a bit appears the first time, it will be set in ones. If it appears the second time, it moves to twos while being removed from ones. When it appears the third time, it is cleared from both ones and twos using a common mask. This helps in removing all bits that occur thrice, hence leaving behind the unique element.
Code
C
C++
Java
Python
C#
JavaScript
TypeScript
Complexity
Time Complexity: O(n) - where n is the number of elements in the array.
Space Complexity: O(1) - as only a fixed amount of space is used regardless of the input size.
Approach 2: Use a Map to Count Frequencies
This approach involves using a data structure to count occurrences of each number. Although this uses linear time complexity, it requires additional memory to store frequencies, which violates the constant space constraint.
This implementation sorts the array first, which costs O(n log n) time, and then iterates over it checking for numbers that do not repeat thrice by comparison. Although simple, this technique also requires modification of the input if sorting is destructive.
Complexity
Time Complexity: O(n log n) - primarily due to the sorting step.
Space Complexity: O(1) - if in-place sort is assumed.
Approach 3: Bitwise Operation
We can enumerate each binary bit i, and for each binary bit, we calculate the sum of all numbers on that bit. If the sum of the numbers on that bit can be divided by 3, then the number that only appears once on that bit is 0, otherwise it is 1.
The time complexity is O(n times log M), where n and M are the length of the array and the range of elements in the array, respectively. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
JavaScript
Rust
C
Swift
Approach 4: Digital Circuit
We can use a more efficient method that uses digital circuits to simulate the above bitwise operation.
Each binary bit of an integer can only represent 2 states, 0 or 1. However, we need to represent the sum of the i-th bit of all integers traversed so far modulo 3. Therefore, we can use two integers a and b to represent it. There are three possible cases:
- The
i-th bit of integerais 0 and thei-th bit of integerbis 0, which means the modulo 3 result is 0; - The
i-th bit of integerais 0 and thei-th bit of integerbis 1, which means the modulo 3 result is 1; - The
i-th bit of integerais 1 and thei-th bit of integerbis 0, which means the modulo 3 result is 2.
We use integer c to represent the number to be read in, and the truth table is as follows:
a_i |
b_i |
c_i |
New a_i |
New b_i |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
Based on the truth table, we can write the logical expression:
$
a_i = a_i' b_i c_i + a_i b_i' c_i'
and:
b_i = a_i' b_i' c_i + a_i' b_i c_i' = a_i' (b_i \oplus c_i)
The final result is b, because when the binary bit of b is 1, it means that the number appears only once.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1)$.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Rust
Approach 5: Set + Math
Code
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Bit Manipulation | Time Complexity: O(n) - where n is the number of elements in the array. |
| Use a Map to Count Frequencies | Time Complexity: O(n log n) - primarily due to the sorting step. |
| Bitwise Operation | — |
| Digital Circuit | — |
| Set + Math | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Frequency Count | O(n) | O(n) | Good first approach in interviews or when memory constraints are not strict |
| Bit Manipulation (Bit Counting mod 3) | O(n) | O(1) | Optimal solution when constant extra space is required |
Video Solution
L6. Single Number II | Bit Manipulation • take U forward • 168,494 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Single Number II easy or hard?
Single Number II Python/Java solution
How to solve Single Number II in O(n)?
What is the best approach for Single Number II?
Is Single Number II asked at Google/Amazon/Meta?
What data structure is used in Single Number II?
What is the time complexity of Single Number II?
Ready to solve this problem?
Practice Single Number II with our built-in code editor and test cases.
Practice on FleetCode