Given an integer array nums where every element appears exactly three times except for one element, which appears once, find and return that single element.
Your solution must run in linear time and use only constant extra space.
ones, twos) that record how many times, mod 3, each bit has been seen. It's the same constant-space guarantee in a single pass.Input: nums = [2, 2, 3, 2] Output: 3 2 appears three times and cancels column-by-column; 3 is the single value.
Input: nums = [0, 1, 0, 1, 0, 1, 99] Output: 99 0 and 1 each appear three times; 99 is the only element appearing once.
Input: nums = [1] Output: 1 A lone element is trivially the single one.
- 1 <= nums.length <= 3 * 10^4 - -2^31 <= nums[i] <= 2^31 - 1 - Every element appears exactly three times except for one element which appears once.
In the previous problem, values came in pairs and XOR wiped them out because a bit seen twice returns to 0. Now they come in threes — and XOR breaks, because a bit seen three times is still 1. The fix is to stop thinking in "even/odd" (mod 2) and start counting each bit column mod 3.
0s and 1s.mod 3 erases anything that appears a multiple of three times.“Does exactly one element appear once, the rest exactly three times?”
Yes — that's the promise, so the answer is uniquely defined.
“Can values be negative?”
Yes, across the full 32-bit signed range, so the sign bit must be handled.
“What space am I allowed?”
Constant extra space — so a frequency map, while correct, isn't the intended answer.
Last time pairs cancelled under XOR — but XOR only tracks a bit mod 2, so triples don't vanish.
So I'll count each bit position across all numbers and take that count mod 3.
A tripled value adds 0 or 3 to a column, so mod 3 it contributes nothing — only the loner's bits survive.
Worked example — nums = [2, 2, 3, 2] (bit columns, low bit on the right)
2 -> 1 0 2 -> 1 0 3 -> 1 1 2 -> 1 0 ------------ col sum: 4 1 mod 3: 1 1 -> binary 11 = 3
XOR collapses a bit column to its parity. Two copies cancel, but three copies leave a 1 behind. For triples you need the count mod 3, not mod 2.
In every bit position, a value appearing three times contributes 0 or 3 — a multiple of three. So column_sum % 3 is untouched by the triples and equals the single number's bit at that position.
Looping positions 0–31 reconstructs a 32-bit pattern. If bit 31 ends up set, the answer is negative — so read the pattern back as a signed 32-bit integer (e.g. subtract 2^32, or store it in an int).
| Frequency map | Count bits mod 3 | |
|---|---|---|
| Idea | Tally occurrences, return the key seen once | Per bit position, sum the column mod 3 |
| Time | O(n) | O(32n) = O(n) |
| Space | O(n) | O(1) |
Both are linear; only the bit-counting approach meets the constant-space bar. Full code is in the Approaches selector below.
Key takeaway
XOR is "count each bit mod 2." When duplicates come in threes, count each bit mod 3 instead — the tripled values fall away and the loner's bits remain. This "count bits mod k" idea is the general key to the whole Single Number family.
res = 0
for bit position i in 0..31:
ones = number of nums with bit i set
if ones % 3 != 0:
set bit i of res
reinterpret res as a signed 32-bit integer
return res