Single Number II
Understanding the Problem
You have an array where every number appears exactly three times, except one number that appears once. The task is to find that single number.
In the classic Single Number problem (LeetCode 136), every duplicate appears twice, so XOR of all elements cancels the pairs and leaves the unique one. XOR cancels in pairs, not triples, so that technique does not transfer here.
The problem is how to cancel out elements that appear three times. The approaches below go from counting occurrences directly to a bit manipulation method that processes each bit position independently and meets the O(1) space requirement.
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
Count how many times each number appears, then return the one with a count of 1. A hash map records the counts in a single pass.
This does not meet the O(1) space requirement, but it gives a correct baseline that the bit-manipulation approaches can be measured against.
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 uses O(n) extra space. The next approach reaches the answer without storing every element, by working one bit position at a time.
Approach 2: Bitwise Counting (Bit-by-Bit)
Intuition
Instead of working with whole numbers, work with each bit position independently.
Take a single bit position, say bit 0 (the least significant bit). Across all elements, each number that appears three times contributes either 0 or 3 to the 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.
Negative numbers need no special handling, because the count operates on the raw bit representation. In two's complement, the sign bit (bit 31) is one more bit position, and the same mod-3 logic applies. Reconstructing a number with bit 31 set produces a negative value in a signed 32-bit type, which is the result wanted.
Algorithm
- For each bit position from 0 to 31:
- Count how many numbers in the array have a 1 at this bit position.
- Take the count modulo 3.
- 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 achieves O(n) time and O(1) space, but it makes 32 passes over the array. The next approach processes all 32 bits in a single pass using two bitmasks.
Approach 3: Bitmask State Machine (ones, twos)
Intuition
Instead of counting bits one position at a time, process all 32 bits in parallel during a single pass, using a mod-3 counter that operates on entire integers at once.
Each bit position needs a counter that cycles through 0, 1, 2, and back to 0. Representing three states (0, 1, 2) takes two bits, so two variables hold them: 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.
After processing all numbers, every tripled element's bits have cycled back to (0,0), so ones holds only the single number's bits, in state (1,0).
The two update lines are not interchangeable. The first line updates ones, and the second line masks twos with the already updated ones. This guarantees ones and twos never both carry a 1 at the same bit position, which is what keeps the three-state cycle valid. Swapping the lines, or computing both from the old values, breaks the invariant and gives a wrong answer.
Algorithm
- Initialize
ones = 0andtwos = 0. - For each number in the array:
- Update
ones: XOR with the number, then mask out any bits that are intwos. - Update
twos: XOR with the number, then mask out any bits that are inones. - 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.