Single Number II

Single Number II

What is this problem about?

Building on the original "Single Number" problem, "Single Number II" introduces a new layer of complexity. Here, every element in the array appears exactly three times, except for one element that appears only once. You are still tasked with finding the unique element in O(n) time and O(1) space. This "Single Number II coding problem" moves from simple bitwise tricks to more advanced bit counting techniques.

Why is this asked in interviews?

Companies like Bloomberg and Amazon ask this to see if you can generalize bitwise logic. The simple XOR trick no longer works because XORing a number three times is the same as XORing it once (x ^ x ^ x = x). This problem tests if you can think about integers at the bit level—counting the occurrences of each bit across all numbers. It's a true test of mathematical intuition and bitwise proficiency.

Algorithmic pattern used

The "Bit Manipulation and Bit Counting interview pattern" is used here. For each of the 32 bits (assuming standard integers), you count how many numbers in the array have that bit set. Since every number (except the unique one) appears three times, the sum of bits at any position should be a multiple of three if the unique number doesn't have that bit set. If the sum is 3k + 1, it means the unique number does have that bit set. By checking all 32 bit positions, you can reconstruct the single number.

Example explanation

Array: [2, 2, 3, 2]

1. Binary of 2: 0010
2. Binary of 3: 0011

• Bit 0 count: 2 (from 2) has bit 0 as 0. 3 has bit 0 as 1. Counts: 0 + 0 + 1 + 0 = 1. 1 % 3 = 1. So, result bit 0 is 1.
• Bit 1 count: 2 (from 2) has bit 1 as 1. 3 has bit 1 as 1. Counts: 1 + 1 + 1 + 1 = 4. 4 % 3 = 1. So, result bit 1 is 1.
• Other bits: All counts are 0. 0 % 3 = 0. The reconstructed result is ...0011, which is 3.

Common mistakes candidates make

The most frequent error is applying the simple XOR approach, which fails here. Another challenge is handling negative numbers; in languages like Python, bitwise operations on negative numbers can be tricky due to how they represent arbitrary-precision integers. Many candidates also find it difficult to implement the "sum of bits" logic using only a few variables, often resorting to an array of size 32, which is technically O(1) space but less elegant than pure bitwise state machines.

Interview preparation tip

When the simple XOR pattern fails for frequency problems, look at bitwise sums. If elements appear k times, the sum of bits at each position modulo k will reveal the bits of the unique element. This general principle can solve any variation of the "Single Number II interview question".