TL;DR
Count set bits per position mod 3 (or run a two-variable ones/twos state machine) — O(n) time, O(1) space.
Approach 1 — Hash-map count (brute force)
Count how many times each value occurs, then return the one whose count is 1. Correct and obvious, but the count table is extra space proportional to the number of distinct values — it violates the O(1)-space requirement.
from collections import Counter
from typing import List
def singleNumber(nums: List[int]) -> int:
counts = Counter(nums)
for value, freq in counts.items():
if freq == 1:
return value
return -1 # guaranteed unreachable by the constraints
Complexity: O(n) time, O(n) space.
Time is fine; the space is the problem. An arithmetic variant — (3 * sum(set(nums)) - sum(nums)) // 2 — still builds set(nums), so it is also O(n) space.
Approach 2 — Count 1-bits per position, mod 3 (the bit-level insight)
Reason one bit column at a time. Line the numbers up in binary and look down a single column, bit position i. Every value that appears three times puts the same bit in that column three times, so it contributes either 0 or 3 to the column’s total of 1s. The lone value contributes one extra 0 or 1. Therefore
(number of 1s in column i) = 3 * (something) if the lone number's bit i is 0
= 3 * (something) + 1 if the lone number's bit i is 1
so column_sum % 3 is the lone number’s bit at position i. Do this for all 32 columns and reassemble the answer bit by bit. With nums = [2, 2, 3, 2] (2 = 010, 3 = 011):
bit2 bit1 bit0
2 = 0 1 0
2 = 0 1 0
3 = 0 1 1
2 = 0 1 0
sum: 0 4 1
%3 : 0 1 1 -> 011 = 3 <- the answer
The subtlety is the sign bit. In 32-bit two’s complement, bit 31 carries weight -2^31, not +2^31. Python ints are arbitrary precision, so if bit 31 of the answer is set, subtract 2^31 explicitly to land on the correct negative value.
from typing import List
def singleNumber(nums: List[int]) -> int:
result = 0
for i in range(32):
column_sum = 0
for num in nums:
column_sum += (num >> i) & 1 # is bit i set in this number?
bit = column_sum % 3 # the lone number's bit i
if i == 31 and bit: # sign bit set -> negative
result -= (1 << 31)
else:
result |= (bit << i)
return result
Walkthrough on nums = [0, 1, 0, 1, 0, 1, 99] (expect 99 = 1100011):
- Bit 0: values with bit0 set are
1,1,1,99 → sum 4, 4 % 3 = 1. Set bit 0.
- Bit 1: only
99 has bit1 set → sum 1, % 3 = 1. Set bit 1.
- Bits 2,3,4:
99’s bits there are 0; the three 1s already cleared → each sum 0. Skip.
- Bit 5 (
32) and bit 6 (64): 99 = 64 + 32 + 2 + 1, so each has sum 1, % 3 = 1. Set both.
- Bits 7..31: sum
0. Result = 1 + 2 + 32 + 64 = 99.
Complexity: O(32 · n) = O(n) time, O(1) space. Works unchanged for negatives thanks to the sign-bit handling.
Approach 3 — ones/twos state machine (single pass)
Each bit needs a counter that cycles 0 → 1 → 2 → 0 (mod 3), which has three states. Two bitmasks encode that state in parallel across all 32 positions: ones holds the bits seen 1 (mod 3) times, twos holds the bits seen 2 (mod 3) times, and a bit in neither mask has been seen 0 (mod 3) times.
stateDiagram-v2
[*] --> Zero
Zero: seen 0 (ones=0, twos=0)
One: seen 1 (ones=1, twos=0)
Two: seen 2 (ones=0, twos=1)
Zero --> One: bit present
One --> Two: bit present
Two --> Zero: bit present
On each new number:
- a bit enters
ones if it is in the incoming number and not currently in twos (going 0 → 1 or 2 → 0 for that bit, handled together);
- then
twos is updated symmetrically using the freshly computed ones.
When a bit reaches its third occurrence, both masks clear it, so after processing everything the value that appeared once survives in ones.
from typing import List
def singleNumber(nums: List[int]) -> int:
ones, twos = 0, 0
for num in nums:
ones = (ones ^ num) & ~twos
twos = (twos ^ num) & ~ones
return ones
Walkthrough on nums = [2, 2, 3, 2] (expect 3):
| step | num | ones | twos |
|---|
| init | – | 000 | 000 |
| 1 | 010 | 010 | 000 |
| 2 | 010 | 000 | 010 |
| 3 | 011 | 001 | 000 |
| 4 | 010 | 011 | 000 |
After the last step ones = 011 = 3. In Python this also returns the correct negative for answers with the sign bit set, because ~ and ^ operate on the same arbitrary-precision two’s-complement representation on both sides.
Complexity: O(n) time, O(1) space — a single pass with two integer accumulators.
Common pitfalls
- Ignoring the sign bit in Approach 2. Without the
i == 31 special case, a negative answer comes back as a large positive number (e.g. 2^31 - something). Subtract 2^31 when bit 31 survives.
- Only fixing 32 bits when the language has wider ints. Loop exactly
range(32) for the stated 32-bit constraint; looping range(64) on a genuinely 32-bit input would misread the sign.
- Order matters in the state machine.
ones must be updated before twos (and twos uses the new ones). Swapping the two lines breaks the mod-3 cycle.
- Reaching for XOR alone. Plain XOR solves Single Number I (elements twice + one once) because pairs cancel. With triples, XOR does not cancel — you need the mod-3 counting above.
Pattern takeaway
When duplicates come in a fixed multiplicity k and you need O(1) space, count contributions per bit position mod k: each bit column sums to a multiple of k plus the lone element’s bit. The generalization to remember: k = 2 collapses to a single XOR; for k = 3 (or any k) either sum-columns-mod-k directly, or build a small bitmask state machine that cycles 0 → 1 → … → k-1 → 0.