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:
- Runtime: Must be linear .
- Space: Ideally constant space (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 time but uses space where is the number of unique elements. While this solves it easily, it fails the constant space follow-up.
Sorting takes 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:
a ^ a = 0(XORing identical numbers cancels them out).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
- Calculate Global XOR: Iterate through the array once, accumulating the XOR sum of all elements into a variable
xor_sum. At the end,xor_sumequalsA ^ B. - 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 is1. - 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).
- If yes, XOR into one accumulator (say
- 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: . We iterate through the array twice (once for total XOR, once for partitioning). Both are linear passes over
nelements. - Space Complexity: . 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_bitcorrectly isolates a bit regardless of sign. - Minimum Array Size (
len = 2): If the array is exactly[A, B],xor_sumbecomesA ^ 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
intrange).