Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Single Number II
• Main tags: Array, Bit Manipulation
• Core requirement: linear time and constant extra space

What the problem is really asking

The array contains one value that appears exactly once, while every other value appears exactly three times. The obvious Counter or hash-map solution works, but it uses extra memory, so it does not satisfy the strongest version of the problem.

The real challenge is to use the repetition pattern itself. If every repeated number shows up three times, then the useful question is not “which full number is unique?” but “which individual bits survive after groups of three cancel out?”

The easiest optimal idea

Look at one bit position at a time.

For any fixed bit position:

• every number that appears three times contributes either 0 + 0 + 0 or 1 + 1 + 1
• both of those sums are divisible by 3
• only the unique number can leave a remainder after taking the total bit count modulo 3

That means the answer can be reconstructed bit by bit:

1. Count how many numbers have the kth bit set.
2. Compute that count modulo 3.
3. If the remainder is 1, the unique number must have that bit set.

This is already O(n) time because there are only 32 relevant bit positions for a signed integer, and 32 * n is still linear. It is also O(1) extra space because the algorithm only keeps a few counters.

Why this works

The cancellation argument is the whole proof.

Suppose the array is split into two groups:

• all numbers that appear three times
• the one number that appears once

For any bit position, the first group contributes a multiple of 3, because each repeated value contributes that same bit three times. After modulo 3, all of that disappears. The remainder is therefore exactly the bit contributed by the unique number.

That turns the original problem into a much simpler one: reconstruct a number from the remainders of 32 small counting problems.

A second optimal viewpoint

There is another common O(n) and O(1) solution that keeps two bitmasks, often called ones and twos. Each bit moves through three states as it is seen:

• seen once
• seen twice
• cleared after the third time

This works like a tiny finite-state machine running independently for every bit position. It is elegant and interview-worthy, but the modulo-3 counting approach is easier to derive and easier to explain under pressure, so it is a good primary answer unless the interviewer specifically asks for the bitmask trick.

Python solution

The implementation below uses per-bit counting because it is the clearest constant-space solution.

The only subtle part is negative numbers in Python. Python integers are not limited to 32 bits, but LeetCode expects normal signed integer behavior. The code therefore rebuilds the answer in 32 bits and then converts it back to a signed value if the sign bit is set.

from typing import List


BIT_WIDTH = 32
SIGN_BIT_INDEX = BIT_WIDTH - 1
UNSIGNED_MASK = (1 << BIT_WIDTH) - 1
SIGN_BIT_VALUE = 1 << SIGN_BIT_INDEX
SIGNED_MODULUS = 1 << BIT_WIDTH


def is_bit_set(value: int, bit_index: int) -> bool:
    """Return True when the given 32-bit position contains a 1."""
    return ((value >> bit_index) & 1) == 1


def to_signed_32_bit(value: int) -> int:
    """
    Convert an unsigned 32-bit integer into Python's signed integer form.

    Example:
    0xFFFFFFFF should become -1, not 4294967295.
    """
    if value & SIGN_BIT_VALUE:
        return value - SIGNED_MODULUS
    return value


def find_single_number(numbers: List[int]) -> int:
    """
    Return the value that appears once when every other value appears three times.

    Time: O(32 * n) = O(n)
    Space: O(1)
    """
    reconstructed_value = 0

    for bit_index in range(BIT_WIDTH):
        set_bit_count = 0

        for number in numbers:
            if is_bit_set(number, bit_index):
                set_bit_count += 1

        if set_bit_count % 3 != 0:
            reconstructed_value |= 1 << bit_index

    reconstructed_value &= UNSIGNED_MASK
    return to_signed_32_bit(reconstructed_value)


class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        """LeetCode entry point."""
        return find_single_number(nums)

Interview follow-ups

Can you solve it without iterating over all 32 bit positions?

Yes. The standard alternative keeps two bitmasks that track which bits have been seen once and twice so far. When a bit is seen the third time, it is cleared from both masks. Conceptually, each bit cycles through counts modulo 3, so the masks act like a compact state machine. This still runs in O(n) time and O(1) space, and it avoids the explicit 32-bit loop. The tradeoff is readability: the bitmask transitions are harder to derive on the spot, while bit counting is much easier to justify.

What changes if every other number appears k times instead of 3 times?

The bit-counting solution generalizes cleanly. For each bit position, count how many numbers contribute a 1 and take that total modulo k. Any value appearing exactly k times disappears under modulo arithmetic, so the remainder still comes from the exceptional value. The overall structure stays the same, but the implementation becomes more complicated if the interviewer also changes how many times the unique value appears. In that case, the remainder rule has to match the exact repetition pattern.

How do you handle negative numbers correctly in Python?

That is the main language-specific edge case. Python integers have unlimited precision, so negative values are not automatically restricted to 32 bits. The safest approach is to reconstruct the answer across exactly 32 positions, then inspect the sign bit. If bit 31 is set, subtract 2^32 to convert the unsigned reconstruction into the expected signed result. This preserves the correct answer for cases like [-2, -2, -2, -7], where the unique value is also negative.

If extra space were allowed, what simpler solution would you mention first?

The simplest explanation would be a frequency map. Count each number, then return the one whose count is 1. That solution is easy to write and easy to verify, but it uses O(n) extra space, so it misses the stronger constraint. In an interview, it can still be worth mentioning briefly because it shows clear baseline reasoning before moving to the constant-space version.