Single Number II LeetCode 137 Deep Dive

LeetCode 137 Single Number II presents an integer array where every element appears exactly three times except for exactly one element that appears only once. Your task is to find that unique element. The brute-force approach of counting occurrences with a hash map solves this in O(n) time but uses O(n) space — and the problem explicitly demands O(1) extra space.

The O(1) space constraint rules out hash maps, sorting, and any auxiliary data structure that scales with input size. You need a mathematical or bitwise technique that processes numbers in place and accumulates state using only a fixed number of variables regardless of input size.

The challenge compared to Single Number I (LeetCode 136) is that pairs cancel neatly with XOR — every bit that appears twice becomes 0 — but triplets do not. A bit that appears three times passes through the XOR filter unchanged, so naive XOR returns the unique element only when duplicates come in pairs.

XOR is the perfect tool for pairs because any bit XORed with itself twice becomes 0: a ^ a = 0. This means XOR-ing all elements in Single Number I leaves only the unpaired bit pattern — the unique element. The key property is that XOR counts bits mod 2, and pairs reduce to 0 mod 2.

For triplets the mod changes to 3. A bit that appears three times satisfies count mod 3 = 0 — it should vanish. But XOR gives 1 ^ 1 ^ 1 = 1 (XOR counts mod 2, not mod 3), so a bit appearing three times does NOT cancel out. The three XOR operations return a 1 where we needed a 0.

To cancel bits that appear three times, we need arithmetic mod 3, not mod 2. Each bit position must independently track whether it has been seen 0, 1, or 2 times mod 3. When the count reaches 3 (i.e., 0 mod 3), that bit resets to zero. Two bits of state per position are needed — which is exactly what the ones and twos variables provide.

Before reaching the optimal state machine, it helps to understand the bit-counting approach. For each of the 32 bit positions (or 64 for 64-bit integers), count how many numbers in the array have a 1 at that position. Take that count modulo 3. If the result is 1, the unique number has a 1 at that bit position; if 0, it has a 0.

This works because every repeated element contributes its bit either 0 or 3 times to any given position. Three contributions mod 3 equals 0, so repeated elements vanish. The only remaining 1s in the mod-3 counts come from the unique element, perfectly reconstructing it bit by bit.

The bit counting approach runs in O(32 * n) = O(n) time and O(1) space, satisfying both constraints. It is straightforward to implement and easy to verify. The state machine approach we cover next achieves the same complexity but processes all 32 bit positions simultaneously in a single pass, making it more elegant and slightly faster in practice.

The state machine approach uses two integer variables — ones and twos — as a pair of 32-bit arrays of 2-bit counters. The variable ones holds bits that have appeared 1 mod 3 times across all positions simultaneously. The variable twos holds bits that have appeared 2 mod 3 times. When a bit appears a third time, it clears from both ones and twos, returning to state 00.

The update rules are: ones = (ones ^ num) & ~twos and twos = (twos ^ num) & ~ones. The XOR with num flips the bits where num has a 1, advancing the counter state. The AND NOT mask clears bits that have just reached the third state in the other variable, enforcing the mod-3 rollover. These two lines together implement all four state transitions in a single pass.

After processing every number in the input, ones contains exactly the bits that appeared 1 mod 3 times across all elements. Since every element except the unique one appears exactly 3 times (0 mod 3), ones holds only the bits of the unique element. The answer is simply the value of ones at the end.

Consider nums = [2, 2, 3, 2]. In binary: 2 = 010, 3 = 011. The number 2 appears three times and 3 appears once, so the answer should be 3. Let us trace the state machine step by step starting with ones = 0 and twos = 0.

After num = 2 (010): ones = (0 ^ 2) & ~0 = 2 & 0xFFFF = 010; twos = (0 ^ 2) & ~2 = 2 & ~2 = 0. State: ones=010, twos=000. After num = 2 again: ones = (010 ^ 010) & ~000 = 000; twos = (000 ^ 010) & ~000 = 010. State: ones=000, twos=010.

After num = 3 (011): ones = (000 ^ 011) & ~010 = 011 & 101 = 001; twos = (010 ^ 011) & ~001 = 001 & 110 = 000. State: ones=001, twos=000. After num = 2 (010): ones = (001 ^ 010) & ~000 = 011; twos = (000 ^ 010) & ~011 = 010 & 100 = 000. State: ones=011, twos=000. Result: ones = 011 = 3. Correct!

The state machine solution in Python is remarkably compact. Initialize ones = 0 and twos = 0, then loop through each num in nums applying the two update lines: ones = (ones ^ num) & ~twos followed immediately by twos = (twos ^ num) & ~ones. Note the order matters — ones must be updated first. Return ones. Time: O(n), Space: O(1).

Java handles the same logic identically since Java integers are fixed 32-bit two's complement. Use int ones = 0, twos = 0; then in the loop: ones = (ones ^ num) & ~twos; twos = (twos ^ num) & ~ones;. Return ones. The bitwise operators behave the same in both languages for positive numbers; the difference appears only with negative unique elements in Python.

The bit-counting version is also O(n) O(1) but uses a nested loop over 32 bit positions. For each bit b, sum up (num >> b) & 1 for all nums, then set result bit b to that sum % 3. Reconstruct the result integer from the 32 bits. Both approaches solve the problem; the state machine is the interview-expected elegant solution.

Single Number II belongs to the bit state machine family. Single Number I (LeetCode 136) is the simpler XOR version where pairs cancel cleanly. Single Number III (LeetCode 260) extends the XOR idea to two unique elements using a partition trick on the XOR of both unique numbers. These three problems together form a complete tour of bit cancellation techniques.

Missing Number (LeetCode 268) uses XOR-with-index to find the one missing value in a range — a related technique where XOR cancels matched pairs (index-value pairs) and leaves the unmatched one. Counting Bits (LeetCode 338) and Number of 1 Bits (LeetCode 191) reinforce the bit-by-bit thinking that underlies the mod-3 counting approach. Sum of Two Integers without the + operator uses the same XOR-plus-carry bitwise pattern.

The broader bit state machine family includes problems like Find the Duplicate Number and Single Element in a Sorted Array, where each requires a different trick to isolate the outlier element. Mastering the transition from mod-2 (XOR) to mod-3 (ones/twos state machine) to mod-k (generalized state machine) gives a powerful toolkit for any problem asking for a single outlier among uniformly repeated elements.