Problem Description

You are given an integer array nums where every element appears three times except for one element, which appears exactly once. Your task is to find and return that single element.

The challenge has two important constraints:

• Your solution must have linear runtime complexity (O(n))
• Your solution must use only constant extra space (O(1))

For example, if nums = [2, 2, 3, 2], the answer would be 3 since it appears only once while 2 appears three times.

The key insight is to use bitwise operations. Since every number except one appears exactly three times, we can examine each bit position across all numbers. For any given bit position, if we count how many numbers have a 1 in that position, the count will either be divisible by 3 (if the single number has 0 in that position) or have a remainder of 1 when divided by 3 (if the single number has 1 in that position).

The solution iterates through all 32 bit positions (for a 32-bit integer), counts the number of 1s at each position across all numbers, and reconstructs the single number bit by bit. Special handling is needed for the sign bit (position 31) to correctly handle negative numbers.

Intuition

Let's think about what happens when numbers appear multiple times. If we had pairs (each number appearing twice), we could use XOR since a ^ a = 0. But with triplets, XOR doesn't directly help.

Consider looking at the problem from a different angle - what if we examine each bit position independently? Let's say we have [5, 5, 5, 3] in binary:

• 5 = 101
• 5 = 101
• 5 = 101
• 3 = 011

For bit position 0 (rightmost): we have three 1s from the 5s and one 1 from 3, totaling 4. Since 4 % 3 = 1, we know the single number has a 1 at position 0.

For bit position 1: we have zero 1s from the 5s and one 1 from 3, totaling 1. Since 1 % 3 = 1, the single number has a 1 at position 1.

For bit position 2: we have three 1s from the 5s and zero from 3, totaling 3. Since 3 % 3 = 0, the single number has a 0 at position 2.

This gives us 011 in binary, which is 3 - our answer!

The pattern emerges: for any bit position, if the total count of 1s is divisible by 3, then all the 1s come from the numbers that appear three times, meaning our single number has 0 at that position. If there's a remainder of 1 when dividing by 3, our single number contributes that extra 1.

By processing all 32 bit positions this way, we can reconstruct the single number bit by bit, using only constant space to store our result and a counter for each bit position.

Solution Approach

The implementation uses bitwise operations to examine each of the 32 bit positions individually:

1. Initialize the result: Start with ans = 0 to build our answer bit by bit.

2. Iterate through each bit position: Loop through positions 0 to 31 (covering all bits in a 32-bit integer).

3. Count bits at each position: For bit position i, count how many numbers have a 1 at that position:

   • num >> i shifts the number right by i positions
   • & 1 isolates the bit at position 0 after shifting
   • sum(num >> i & 1 for num in nums) counts total 1s at position i

4. Determine the bit value: If cnt % 3 is non-zero (has remainder 1), the single number has a 1 at position i:

   • For positions 0-30: Use ans |= 1 << i to set bit i to 1
   • For position 31 (sign bit): Use ans -= 1 << 31 to handle negative numbers correctly

5. Handle negative numbers: The special case for bit 31 is crucial. If the single number is negative, its 31st bit is 1. In Python's two's complement representation, setting the sign bit requires subtracting 1 << 31 rather than using OR operation.

The algorithm processes each number exactly once for each bit position, giving us O(32n) = O(n) time complexity. We only use a few variables (ans, i, cnt), achieving O(1) space complexity.

For example, with nums = [2, 2, 3, 2]:

• Bit 0: count = 4, 4 % 3 = 1, so bit 0 is 1
• Bit 1: count = 3, 3 % 3 = 0, so bit 1 is 1
• Result: 11 in binary = 3 in decimal

Example Walkthrough

Let's walk through the algorithm with nums = [5, 5, 5, 3]:

Step 1: Convert to binary for visualization

• 5 = 00000101 (showing 8 bits for simplicity)
• 3 = 00000011

Step 2: Process each bit position

Starting with ans = 0:

Bit position 0 (rightmost):

• Check each number: 5 & 1 = 1, 5 & 1 = 1, 5 & 1 = 1, 3 & 1 = 1
• Count = 4 ones
• 4 % 3 = 1 (remainder exists)
• Set bit 0 of ans: ans = 0 | 1 = 1

Bit position 1:

• Check each number: (5 >> 1) & 1 = 0, (5 >> 1) & 1 = 0, (5 >> 1) & 1 = 0, (3 >> 1) & 1 = 1
• Count = 1 one
• 1 % 3 = 1 (remainder exists)
• Set bit 1 of ans: ans = 1 | (1 << 1) = 1 | 2 = 3

Bit position 2:

• Check each number: (5 >> 2) & 1 = 1, (5 >> 2) & 1 = 1, (5 >> 2) & 1 = 1, (3 >> 2) & 1 = 0
• Count = 3 ones
• 3 % 3 = 0 (no remainder)
• Don't set bit 2, ans remains 3

Bit positions 3-31:

• All have count = 0
• 0 % 3 = 0 (no remainder)
• No bits set, ans remains 3

Final result: ans = 3

The algorithm correctly identifies that the single number is 3 by reconstructing it bit by bit based on which bit positions have counts not divisible by 3.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × 32) which simplifies to O(n), where n is the length of the array. The code iterates through 32 bits (fixed constant for integer representation), and for each bit position, it performs a sum operation that traverses all n elements in the array. Since 32 is a constant, the overall time complexity is O(n).

The reference answer mentions O(n × log M) where M is the range of elements. This is equivalent because log M represents the number of bits needed to represent the maximum value in the array. For 32-bit integers, this is at most 32, so log M ≤ 32.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space for variables ans, i, and cnt, regardless of the input size. No additional data structures that grow with input size are created.

Common Pitfalls

1. Incorrect Handling of Negative Numbers

The most common pitfall in this problem is failing to properly handle negative numbers when reconstructing the result bit by bit. Many developers mistakenly treat bit 31 (the sign bit) the same as other bits.

Incorrect approach:

# Wrong: Treating bit 31 like any other bit
if bit_count % 3:
    result |= (1 << bit_position)  # This doesn't work correctly for bit 31

Why it fails: In Python's integer representation, directly ORing with 1 << 31 doesn't produce the correct negative number due to Python's arbitrary precision integers. The value 1 << 31 equals 2147483648, and ORing this creates a large positive number instead of a negative one.

Correct approach:

if bit_count % 3:
    if bit_position == 31:
        result -= (1 << 31)  # Subtract to create negative number
    else:
        result |= (1 << bit_position)

2. Alternative Solution Using State Machine

Another approach uses a state machine with two variables to track bit counts modulo 3:

def singleNumber(self, nums: List[int]) -> int:
    ones = 0   # Bits that have appeared once (mod 3)
    twos = 0   # Bits that have appeared twice (mod 3)
  
    for num in nums:
        # Update twos: add bits from ones that are also in num
        twos |= ones & num
      
        # Update ones: XOR with num to toggle bits
        ones ^= num
      
        # Clear bits that have appeared three times
        # (bits that are in both ones and twos)
        threes = ones & twos
        ones &= ~threes
        twos &= ~threes
  
    return ones

This approach avoids the sign bit issue entirely by using bitwise operations that naturally preserve sign information, making it more elegant and less error-prone for handling negative numbers.