Single Number II LeetCode Solution: Bit Counting Walkthrough

Single Number II (#137) is one of those problems that looks deceptively similar to its easier sibling. If you solved Single Number (#136) with XOR, you might assume the same trick works here. It does not. This is the problem where the single number ii leetcode pattern forces you to think at the bit level.

The setup is almost identical: given an integer array where every element appears exactly three times except one element that appears once, find that unique element. The twist is the "three times" constraint — XOR cancels pairs but not triples, so you need a fundamentally different approach.

This walkthrough covers why XOR fails, how the bit counting modulo 3 technique works, the full implementation, edge cases interviewers test, and why this pattern generalizes far beyond this single problem.

You are given a non-empty array of integers where every element appears exactly three times except for one element that appears exactly once. Find and return that single element. The constraint: your algorithm should have O(n) time complexity and O(1) space complexity.

The O(1) space requirement is what makes this problem interesting. Without it, you could use a hash map to count frequencies in O(n) time and O(n) space. The challenge is doing it with only a constant number of variables, regardless of input size.

This is a Medium-difficulty problem, but it tests a technique — bit-level counting — that many candidates have never encountered. Understanding it deeply gives you a tool that works for an entire family of "find the unique element" problems.

In Single Number (#136), every element appears twice except one. XOR works perfectly because a ^ a = 0 — pairs cancel out, leaving only the unique element. XOR the entire array and you are done in one pass.

But what happens when elements appear three times? XOR does not cancel triples. If you XOR a number with itself three times, you get: a ^ a ^ a = a. The third XOR undoes the cancellation. So XORing the entire array leaves you with a mess of overlapping bits, not the clean single element you need.

This is the critical insight: XOR is a modulo-2 operation. It counts each bit position modulo 2, which is why pairs vanish. For triples, you need a modulo-3 operation. And that is exactly what the bit counting approach provides.

The bit counting technique works by examining each of the 32 bit positions independently. For each bit position, count how many numbers in the array have that bit set to 1. If every number appeared exactly three times, the count at every position would be divisible by 3.

But one number appears only once. So at any bit position where the unique number has a 1, the total count will be 3k + 1 (where k is the number of triple-appearing numbers with that bit set). If count % 3 equals 1, the unique number has that bit set. If count % 3 equals 0, it does not.

Reconstruct the unique number by checking all 32 bit positions. For each position where count % 3 is not zero, set that bit in the result. This runs in O(32n) = O(n) time and uses O(1) space — just a few integer variables for the loop counters and result.

The implementation is straightforward once the concept clicks. Use an outer loop over 32 bit positions (0 through 31). For each bit position, use an inner loop over the entire array to count how many numbers have that bit set. If the count modulo 3 is not zero, set that bit in the result.

To check if bit i is set in a number, use (num >> i) & 1. This shifts the number right by i positions and masks everything except the lowest bit. To set bit i in the result, use result |= (1 << i). The bitwise OR flips that bit on without affecting the others.

The time complexity is O(32n) which simplifies to O(n). The space complexity is O(1) — you use only the result variable, a bit position counter, and a count variable. This is the optimal leetcode 137 solution that satisfies the O(1) space constraint.

The bit counting approach handles all edge cases cleanly, but interviewers will ask about them.

Unique element is 0: Every bit count will be divisible by 3, so no bits get set in the result. The result stays 0, which is correct. Single element array: The one element is the unique element. Every bit it has produces a count of 1, and 1 % 3 = 1, so all its bits get set in the result.

Negative numbers require care with the sign bit. In languages with 32-bit signed integers, bit 31 is the sign bit. The modulo-3 counting works identically on the sign bit — if the unique number is negative, bit 31 will have count % 3 = 1, and the result will be negative. No special handling is needed because bitwise operations treat all 32 bits uniformly.

Large arrays with many repeated triples: The approach scales linearly. Each number is examined 32 times (once per bit position), but the constant factor is small. For arrays with millions of elements, this is efficient and cache-friendly.

The bit counting modulo K technique is one of the most elegant generalizations in bit manipulation. Once you understand it for K=3, you can solve any "every element appears K times except one" variant instantly. Change the modulus, and the same approach works for K=4, K=5, or any positive integer.

This technique also builds the foundation for Single Number III (#260), where two numbers appear once and all others appear twice. That problem combines XOR with bit manipulation in a different way, but the bit-level thinking you develop here transfers directly.

Practice this problem until the bit counting setup — outer loop over 32 positions, inner loop counting set bits, modulo check, OR into result — becomes automatic. YeetCode flashcards help you drill the single number ii leetcode pattern so the technique is instant recall when you see any "find the unique element" problem in your next interview.