Single Number II
Single Number II: every element of nums appears exactly three times except for one, which appears once. Return that single element in linear time and constant extra space.
- 1 <= nums.length <= 3 * 10⁴
- -2³¹ <= nums[i] <= 2³¹ - 1
- Each element in nums appears exactly three times except for one element which appears once.
Intuition
XOR solved the two-copies version because a ^ a = 0 — pairs erase themselves. In single number ii three copies do not erase, so the whole trick collapses and we need a different cancellation. Drop a level of abstraction and look at a single bit column across all the numbers. A value appearing three times contributes either three ones or zero ones to that column — in both cases a multiple of three. So the count of ones in each column, taken modulo 3, is exactly what the single number contributes there. Rebuild the answer column by column.
XOR can't help when values repeat three times, so count each bit position independently. Bits belonging to tripled numbers occur a multiple of 3 times; whatever remains modulo 3 belongs to the single value. Per-bit counting generalises to any repeat count.
Approach
Before reading on: price up what counting everything costs here, then ask which operator makes the unwanted values cancel themselves out. Aim for O(32n) = O(n) time and O(1) space.
Start with the hash map so you know what you are replacing
The obvious solution counts frequencies in a map and returns the key whose count is 1. It is O(n) time, which is already optimal — but it costs O(n/3) space, and that space is the entire point of the problem. Knowing this baseline matters in an interview: state it, give its complexity, then say why the interviewer will push back on it.
Look at one bit column instead of one number
Stack the values in binary. For [5,5,5,2,4,4,4] that is 101, 101, 101, 010, 100, 100, 100. Read down the rightmost column: three ones, all from the fives. Next column: one, from the two. Next: six, from the fives and fours. Every column's count is a multiple of three plus whatever the lone number contributes — a cancellation rule that survives triples, which XOR could not give us.
Take each column count mod 3 and reassemble
For each of the 32 bit positions, count how many numbers have that bit set. count % 3 == 1 means the single number has that bit, so OR 1 << i into the answer. Thirty-two passes is O(32n) = O(n) with O(1) space. With signed 32-bit ints, handle bit 31 by reading the assembled value as signed — in Python, subtract 1 << 32 when bit 31 comes out set.
Solution & live demo
Common pitfalls
Using XOR
for n in nums: ans ^= n
if count % 3:
ans |= (1 << i)XOR annihilates pairs, but three copies of a value leave one copy behind, which mixes into the result. Only counting modulo the repeat factor isolates the single.
Not sign-correcting the result
return ans
if ans >= (1 << 31):
ans -= (1 << 32)
return ansPython integers are unbounded, so setting bit 31 produces a large positive number instead of a negative one. The manual two's-complement fix-up is needed for negative answers; C++ and Java get it for free from fixed-width ints.
Counting over the wrong bit width
for i in range(max(nums).bit_length()):
for i in range(32):
Negative inputs have high bits set that bit_length on the maximum never reaches, so those positions are never counted and the answer loses its sign information. Fixing the width at 32 covers the stated constraints.
Edge cases
In Python integers are unbounded, so bit 31 must be interpreted manually: if the reconstructed answer has bit 31 set, subtract 1 << 32 to recover the negative value. C++ and Java get this for free from the fixed-width int.
Every column count is a multiple of 3, so no bit is ever set and the answer is 0 — correct, not a failure to find anything.
Each column count is 0 or 1; count % 3 reproduces the bits of the only element exactly.