Domain 2MediumCORE

Single Number III

We are given an array of integers where every element appears exactly twice, except for two specific elements which appear only once. Our goal is to identify and return those two unique numbers. The order in the output doesn't matter.

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

260. Single Number III

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


Problem Breakdown

We are given an array of integers where every element appears exactly twice, except for two specific elements which appear only once. Our goal is to identify and return those two unique numbers. The order in the output doesn’t matter.

Key constraints:

  1. Runtime: Must be linear O(n)O(n).
  2. Space: Ideally constant space O(1)O(1) (per follow-up).

Implicit considerations include handling negative integers correctly, as bitwise operations behave differently with signed numbers compared to unsigned ones in some languages, though Python handles large integers naturally. We also need to ensure we don’t use extra data structures like a hash map or frequency array if possible, given the space constraint requirement.

Intuition

A naive approach would be to count frequencies using a Hash Map (Counter). This gives us O(n)O(n) time but uses O(k)O(k) space where kk is the number of unique elements. While this solves it easily, it fails the constant space follow-up.

Sorting takes O(nlog⁡n)O(n \log n) time and doesn’t meet linear requirements strictly speaking for large inputs in an interview context (though often acceptable).

The key insight lies in Bitwise XOR properties:

  1. a ^ a = 0 (XORing identical numbers cancels them out).
  2. a ^ b = c. If we XOR all elements together, the duplicates cancel each other to zero, leaving us with just the two unique numbers: result = A ^ B.

Since A != B, their binary representations must differ in at least one bit position. The result of our total XOR (total_xor) will have a 1 only where bits between A and B are different, and 0 otherwise (since duplicates cancel out).

If we find any set bit (a ‘1’) in total_xor, that specific bit distinguishes the two unique numbers. One number has a 0 at this position, the other has a 1. We can use this bit to partition all numbers into two groups: those with 0 and those with 1 at this position. XORing each group separately will isolate one of the unique numbers in each group (since duplicates within that specific subset still cancel out).

Approach

  1. Calculate Global XOR: Iterate through the array once, accumulating the XOR sum of all elements into a variable xor_sum. At the end, xor_sum equals A ^ B.
  2. Find Distinguishing Bit: We need to isolate one bit that is different between A and B. The expression (xor_sum & -xor_sum) isolates the rightmost set bit (the lowest-order ‘1’). This gives us a mask (diff_bit) where only the differing position is 1.
  3. Partition and Solve: Iterate through the array again. For each number, check if it has that specific bit set using (num & diff_bit).
    • If yes, XOR into one accumulator (say res_a).
    • If no, XOR into another accumulator (res_b).
  4. Return: The two accumulators will hold the unique numbers A and B respectively because duplicates within each partition cancel out to zero.

Complexity Analysis

  • Time Complexity: O(n)O(n). We iterate through the array twice (once for total XOR, once for partitioning). Both are linear passes over n elements.
  • Space Complexity: O(1)O(1). We only use a few integer variables (xor_sum, mask, accumulators), regardless of input size.

Solution

def singleNumber(nums):
    # Step 1: XOR all numbers to get (A ^ B). Duplicates cancel out.
    xor_sum = 0
    for num in nums:
        xor_sum ^= num
    
    # Step 2: Isolate the rightmost set bit where A and B differ.
    # -xor_sum is two's complement negation, so this isolates lowest '1'.
    diff_bit = xor_sum & (-xor_sum)
    
    # Step 3: Partition numbers based on that bit and XOR within groups.
    res_a = 0
    res_b = 0
    
    for num in nums:
        if (num & diff_bit):
            res_a ^= num
        else:
            res_b ^= num
            
    return [res_a, res_b]

# Example usage:
print(singleNumber([1,2,1,3,2,5])) # Output: [3, 5] or [5, 3]

Edge Cases Handled

  • Negative Numbers: Python handles bitwise operations on negative integers using two’s complement logic (conceptually infinite leading bits). The mask diff_bit correctly isolates a bit regardless of sign.
  • Minimum Array Size (len = 2): If the array is exactly [A, B], xor_sum becomes A ^ B. Partitioning separates them immediately into two groups containing one element each, returning correct result.
  • Large Integers: Python integers have arbitrary precision; logic holds for values beyond standard 32-bit limits without overflow issues common in fixed-width languages like C++ or Java (though constraints specify within int range).