Single Number II
Last Updated: March 29, 2026
Understanding the Problem
You have an array where every number shows up exactly three times, except one lone number that appears just once. Your job is to find that single number.
If you have seen the classic Single Number problem (LeetCode 136), you know that when every duplicate appears twice, a simple XOR of all elements cancels out the pairs and leaves the unique one. But XOR cancels things in pairs, not triples. So the trick from Single Number does not directly work here.
The key question is: how do we "cancel out" elements that appear three times? The approaches below explore different ways to handle this, from straightforward counting all the way to an elegant bit manipulation trick that processes each bit position independently.
Key Constraints:
1 <= nums.length <= 3 * 10^4— With n up to 30,000, O(n^2) means roughly 900 million operations, which is borderline but likely too slow. O(n log n) is comfortable, and O(n) is ideal.-2^31 <= nums[i] <= 2^31 - 1— Full 32-bit integer range, including negatives. Any bit-level approach needs to handle negative numbers properly (32 bits, two's complement).- The problem explicitly asks for O(n) time and O(1) space, which rules out hash map counting as the final answer and pushes us toward bit manipulation.
Approach 1: Hash Map Counting
Intuition
The most straightforward idea: count how many times each number appears, then find the one with a count of 1. A hash map handles this cleanly in a single pass.
This is how you would solve it in production code. It does not meet the O(1) space requirement the problem asks for, but it is a solid starting point that is easy to reason about and hard to mess up.
Algorithm
- Create a hash map to store the count of each element.
- Iterate through the array, incrementing each element's count.
- Iterate through the hash map and find the element with count equal to 1.
- Return that element.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the array once to build the count map, and then iterate through the map entries. Both passes are linear.
- Space Complexity: O(n). The hash map stores up to n/3 + 1 unique elements, which is O(n).
The hash map approach meets the O(n) time requirement, but it uses O(n) extra space. The problem specifically asks for O(1) space. Can we figure out the answer without remembering every element?
Approach 2: Bitwise Counting (Bit-by-Bit)
Intuition
Here is the key insight: instead of thinking about whole numbers, think about each bit position independently.
Consider a single bit position, say bit 0 (the least significant bit). If you look at that bit across all elements in the array, each number that appears three times contributes either 0 or 3 to the total count of 1s at that position. Either way, the contribution from tripled elements is divisible by 3.
The single number's bit at that position adds either 0 or 1 to the total. So if we take the total count of 1s at bit position 0 and compute count % 3, the remainder tells us what the single number's bit is at that position.
We repeat this for all 32 bit positions, and we reconstruct the single number bit by bit.
The brilliance here is treating each bit position as an independent problem. At any given bit position, the tripled numbers contribute a total count of 1s that is a multiple of 3. The single number adds either 0 or 1 to that total. So total % 3 extracts exactly the single number's contribution at that position.
This works for negative numbers too, because we are operating on the raw bit representation. In two's complement, the sign bit (bit 31) is just another bit position, and the same mod-3 logic applies.
Algorithm
- For each bit position from 0 to 31:
a. Count how many numbers in the array have a 1 at this bit position.
b. Take the count modulo 3.
c. If the remainder is 1, set that bit in the result.
- Return the result.
Example Walkthrough
Code
- Time Complexity: O(32n) = O(n). We iterate through all n elements 32 times (once per bit). Since 32 is a constant, this simplifies to O(n).
- Space Complexity: O(1). We only use a fixed number of variables (result, bitSum, loop counters), regardless of input size.
The bit-by-bit approach already achieves O(n) time and O(1) space, but it makes 32 passes over the array. Can we process all 32 bits simultaneously in a single pass?
Approach 3: Bitmask State Machine (ones, twos)
Intuition
Instead of counting bits one position at a time, we want to process all 32 bits in parallel during a single pass. The idea is to build a "mod-3 counter" that works on entire integers at once.
Think of it this way: for each bit position, we need a counter that cycles through 0, 1, 2, and back to 0. That is a mod-3 counter. To represent three states (0, 1, 2), we need two bits. So we use two variables: ones and twos.
For each bit position independently:
ones = 0, twos = 0means that bit has been seen 0 times (mod 3)ones = 1, twos = 0means that bit has been seen 1 time (mod 3)ones = 0, twos = 1means that bit has been seen 2 times (mod 3)- When the count reaches 3, both reset to 0
The update formulas are:
ones = (ones ^ num) & ~twostwos = (twos ^ num) & ~ones
The XOR toggles bits as if we were doing a simple count. The AND with the complement acts as a mask that prevents a bit from being set in the wrong variable, implementing the three-state cycle. After processing all elements, ones holds the bits that appeared exactly once (mod 3), which is our answer.
The two variables ones and twos together encode a mod-3 counter for each of the 32 bit positions simultaneously. Each time a bit is seen, the state transitions from (0,0) to (1,0) to (0,1) and back to (0,0). After processing all numbers, every tripled element's bits have cycled back to (0,0), and only the single number's bits remain in the ones variable with state (1,0).
The order of the two update lines matters. We update ones first, then use the updated ones to mask twos. This ensures the two variables stay in sync and never both have a 1 at the same bit position.
Algorithm
- Initialize
ones = 0andtwos = 0. - For each number in the array:
a. Update ones: XOR with the number, then mask out any bits that are in twos.
b. Update twos: XOR with the number, then mask out any bits that are in ones.
- After processing all numbers,
onescontains the single number. - Return
ones.
Example Walkthrough
Code
- Time Complexity: O(n). A single pass through the array, with O(1) bitwise operations per element.
- Space Complexity: O(1). Only two integer variables are used regardless of input size.