Domain 2MediumCORE

Single Number II

We are given an array of integers nums. The constraint states that every element appears exactly three times except for one unique element which appears once. Our goal is to identify and return this single number.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Bit Manipulation

137. Single Number II

Model: qwen3.5:9b
Topics: Bit Manipulation
FAANG asked: 1
Acceptance rate: 54.1%


Problem Breakdown

We are given an array of integers nums. The constraint states that every element appears exactly three times except for one unique element which appears once. Our goal is to identify and return this single number.

Inputs: An integer list nums with length between 1 and 3×1043 \times 10^4. Outputs: A single integer representing the non-repeating element. Constraints & Edge Cases:

  • Time Complexity Requirement: The follow-up explicitly asks for linear runtime complexity, meaning we cannot afford an algorithm that is quadratic or worse (like sorting).
  • Space Complexity Requirement: We should aim for O(1)O(1) extra space to satisfy the “without using extra memory” constraint. This rules out a Hash Map approach which uses O(N)O(N) space.
  • Negative Numbers: The input range includes negative integers (−231-2^{31}). In languages like C++ or Java, bitwise operations on negatives require careful handling of two’s complement representation and sign extension. However, in Python, we can treat these as arbitrary precision values where the logic holds naturally without explicit masking for 32-bit boundaries unless strictly required by a fixed-width language simulation.
  • Empty Input: The constraints guarantee nums.length >= 1, so an empty array is not possible per spec, but our code should handle it gracefully (returning nothing or default).

Intuition

A brute-force approach would be to count the frequency of every number using a Hash Map and return the one with a count of 1. While this solves the problem in O(N)O(N) time, it uses O(N)O(N) space for the map, failing the follow-up constraint. Sorting takes O(Nlog⁡N)O(N \log N) time which is also suboptimal compared to linear requirements.

To achieve O(1)O(1) extra memory and O(N)O(N) time, we must look at Bit Manipulation.

Consider a single bit position (e.g., the least significant bit). If we sum up all numbers in that specific column across the entire array:

  • Every number appearing three times contributes either 0 or 3 to this count.
  • The unique number appears once, contributing either 0 or 1.

Therefore, if we take the total count of set bits at any position modulo 3, the remainder will be exactly equal to that bit in the single element (since x(mod3)x \pmod 3 is 00 for multiples of 3 and matches the unique value otherwise).

While iterating through each column (O(1)O(1) columns since integers are fixed-width) works, a more elegant state-machine approach exists. We can track bits using two variables:

  • ones: Tracks bits that have appeared exactly once (modulo 3 count = 1).
  • twos: Tracks bits that have appeared twice (modulo 3 count = 2).

When we encounter the third occurrence of a bit, it should be cleared from both counters. This logic allows us to process each number in one pass without iterating over every bit position explicitly or storing counts for numbers.

Approach

We will use two integer variables ones and twos.

  1. Update ones: We XOR the current number with ones. If a bit is set in both, it cancels out (count becomes even). However, we must ensure that if a bit was already tracked as appearing twice (twos), we don’t accidentally add it back to ones. So, after updating ones, we mask it with the inverse of twos (~twos).
  2. Update twos: Similarly, update twos by XORing with current number and masking out bits that are now in ones.

The order matters: We must clear a bit from both counters when its count reaches three (0 mod 3). The logic (ones ^ num) & ~twos ensures we only add to the “seen once” state if it hasn’t been seen twice yet. If a bit is currently in twos, that means it has appeared twice; seeing it again should clear both states, which happens naturally because masking with ~twos prevents re-adding to ones.

Complexity Analysis

  • Time: O(N)O(N) where NN is the length of nums. We iterate through the array exactly once. Bitwise operations are constant time relative to fixed-width integers (or logarithmic in value, but effectively treated as unit cost here).
  • Space: O(1)O(1). We only use two integer variables (ones and twos) regardless of input size.

Solution

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 'ones' tracks bits that have appeared exactly once (mod 3 count = 1)
        ones = 0
        
        # 'twos' tracks bits that have appeared twice (mod 3 count = 2)
        twos = 0
        
        for num in nums:
            # Update 'ones': 
            # XOR with current number toggles the bit.
            # Mask with ~twos ensures we don't add a bit to 'ones' if it's already tracked as appearing twice ('twos').
            ones = (ones ^ num) & ~twos
            
            # Update 'twos':
            # Similar logic: XOR and mask out bits that are now in the updated state of 'ones'.
            twos = (twos ^ num) & ~ones
            
        return ones

Edge Cases Handled

  • Single Element Array: If nums has length 1, the loop runs once. The unique number is XORed into ones, returned correctly.
  • Negative Numbers: Python handles negative integers as arbitrary precision values with two’s complement logic implicitly for bitwise ops in this context (since duplicates are identical). The cancellation property (A⊕A=0A \oplus A = 0) holds regardless of sign bit representation, so the unique number is isolated correctly even if it is negative.