Problem Description

You're given an integer array where every element appears exactly twice, except for two special elements that appear only once. Your task is to find these two unique elements.

The problem has specific constraints:

• The array contains mostly duplicates (each appearing exactly twice)
• Only two elements are unique (appearing exactly once)
• You can return the two unique elements in any order
• Your solution must run in linear time complexity O(n)
• Your solution must use only constant extra space O(1)

For example, if the input array is [1, 2, 1, 3, 2, 5], the two unique elements are 3 and 5 since:

• 1 appears twice
• 2 appears twice
• 3 appears only once
• 5 appears only once

The challenge is to identify these two unique numbers efficiently without using extra space for tracking occurrences (like a hash map), which makes this a classic bit manipulation problem.

Intuition

Let's think about what happens when we XOR all numbers in the array. Since XOR has the property that a ^ a = 0 and a ^ 0 = a, all the duplicate pairs will cancel out. We'll be left with unique1 ^ unique2 - the XOR of the two unique numbers.

Now we have unique1 ^ unique2, but how do we separate them? The key insight is that since unique1 and unique2 are different numbers, their XOR result must have at least one bit that is 1. This 1 bit represents a position where unique1 and unique2 differ - one has a 0 at that position while the other has a 1.

We can use this differentiating bit to partition the entire array into two groups:

• Group A: numbers that have a 1 at this bit position
• Group B: numbers that have a 0 at this bit position

Here's the crucial observation: since duplicate numbers are identical, both copies of any duplicate will fall into the same group. Meanwhile, unique1 and unique2 will be separated into different groups because they differ at this bit position.

Once we've partitioned the array this way, each group becomes a simpler problem - finding the single unique number among pairs of duplicates. We can XOR all numbers in Group A to get one unique number, and XOR all numbers in Group B to get the other.

To find a differentiating bit efficiently, we use the trick xs & -xs which isolates the rightmost 1 bit in xs (where xs = unique1 ^ unique2). This is called the lowbit operation and gives us a clean way to pick a bit position for partitioning.

Solution Approach

Let's walk through the implementation step by step:

Step 1: XOR all elements

xs = reduce(xor, nums)

We XOR all numbers in the array. Due to XOR properties (x ^ x = 0 and x ^ 0 = x), all duplicate pairs cancel out, leaving us with xs = unique1 ^ unique2.

Step 2: Find the differentiating bit

lb = xs & -xs

This lowbit operation isolates the rightmost 1 bit in xs. Here's how it works:

• If xs = 0110 (binary), then -xs = 1010 (two's complement)
• xs & -xs = 0110 & 1010 = 0010, which isolates the rightmost 1 bit

This bit represents a position where unique1 and unique2 differ.

Step 3: Partition and find the first unique number

a = 0
for x in nums:
    if x & lb:
        a ^= x

We iterate through the array and XOR only the numbers that have a 1 at the differentiating bit position (checked by x & lb). This effectively:

• Groups all numbers based on whether they have 1 or 0 at that bit position
• XORs all numbers in the group that has 1 at that position
• Since duplicates fall into the same group and cancel out, we're left with one of the unique numbers

Step 4: Find the second unique number

b = xs ^ a

Since xs = unique1 ^ unique2 and we've found one unique number a, we can find the other by XORing: b = xs ^ a = (unique1 ^ unique2) ^ unique1 = unique2.

Step 5: Return the result

return [a, b]

The algorithm achieves O(n) time complexity with two passes through the array and O(1) space complexity using only a few variables.

Example Walkthrough

Let's trace through the algorithm with the array [1, 2, 1, 3, 2, 5]:

Step 1: XOR all elements

1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5
= (1 ^ 1) ^ (2 ^ 2) ^ 3 ^ 5    // Rearranging pairs
= 0 ^ 0 ^ 3 ^ 5                 // Pairs cancel out
= 3 ^ 5
= 011 ^ 101 (in binary)
= 110 (which is 6 in decimal)

So xs = 6 (binary: 110)

Step 2: Find the differentiating bit

xs = 110 (binary)
-xs = ...11111010 (two's complement)
xs & -xs = 110 & ...11111010 = 010 (which is 2 in decimal)

So lb = 2 (binary: 010), meaning we'll partition based on the 2nd bit from the right.

Step 3: Partition based on the differentiating bit

Check each number's 2nd bit (using x & lb):

• 1 (binary: 001): 001 & 010 = 000 → Group B (bit is 0)
• 2 (binary: 010): 010 & 010 = 010 → Group A (bit is 1)
• 1 (binary: 001): 001 & 010 = 000 → Group B (bit is 0)
• 3 (binary: 011): 011 & 010 = 010 → Group A (bit is 1)
• 2 (binary: 010): 010 & 010 = 010 → Group A (bit is 1)
• 5 (binary: 101): 101 & 010 = 000 → Group B (bit is 0)

Group A contains: [2, 3, 2] Group B contains: [1, 1, 5]

XOR Group A elements:

a = 0
a = 0 ^ 2 = 2
a = 2 ^ 3 = 1
a = 1 ^ 2 = 3

So a = 3

Step 4: Find the second unique number

b = xs ^ a = 6 ^ 3 = 110 ^ 011 = 101 = 5

Step 5: Return result Return [3, 5] - the two unique numbers we were looking for!

The beauty of this approach is that the duplicate pairs (1,1 and 2,2) automatically ended up in the same groups and canceled themselves out through XOR, leaving only the unique numbers.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because:

• The reduce(xor, nums) operation iterates through all n elements once to compute the XOR of all numbers, taking O(n) time
• The second loop for x in nums: also iterates through all n elements once to separate the two unique numbers, taking O(n) time
• All other operations (xs & -xs, xs ^ a, etc.) are constant time O(1) operations
• Total: O(n) + O(n) + O(1) = O(n)

The space complexity is O(1). This is because:

• The algorithm only uses a fixed number of variables (xs, a, b, lb) regardless of the input size
• No additional data structures that grow with input size are created
• The reduce function operates in-place without creating additional storage proportional to the input

Common Pitfalls

1. Misunderstanding the Lowbit Operation

Many developers struggle with understanding why xs & -xs isolates the rightmost set bit. A common mistake is trying to use other bit operations like xs & 1 (which only checks if the number is odd) or xs >> 1 (which shifts bits).

Why it happens: The two's complement representation (-x) flips all bits and adds 1, which creates a specific pattern that when ANDed with the original number, isolates only the rightmost 1 bit.

Solution: Remember that for any number x:

• -x in binary flips all bits to the left of the rightmost 1 and keeps the rightmost 1 and all 0s to its right unchanged
• When you AND them, only the rightmost 1 survives

2. Incorrect Group Partitioning Logic

A frequent error is using the wrong condition to partition numbers into groups. Some might try if x == lb: or if x ^ lb: instead of if x & lb:.

Why it happens: Confusion about what we're checking - we need to test if a specific bit position is set, not compare values or XOR them.

Solution: Use x & lb which correctly checks if the bit at position lb is set in number x. This returns non-zero (truthy) if the bit is set, and zero (falsy) if it's not.

3. Forgetting Edge Cases

While not common in this specific problem formulation, developers might forget to handle:

• Arrays with exactly 2 elements (both unique)
• Very large arrays where integer overflow might be a concern in other languages (though Python handles big integers automatically)

Solution: Test with minimal cases like [1, 2] and ensure the algorithm still works correctly.

4. Attempting to Optimize Prematurely

Some developers try to combine steps or eliminate the second pass through the array, potentially breaking the algorithm's correctness.

Why it happens: Misunderstanding that we need two passes - one to find the XOR of all elements, and another to partition and find one unique number.

Solution: Stick to the clear two-pass approach. The algorithm is already optimal at O(n) time and O(1) space.

5. Using Wrong XOR Identity

A subtle mistake is misremembering XOR properties, such as thinking x ^ x = 1 or x ^ 0 = 0.

Solution: Remember the fundamental XOR properties:

• x ^ x = 0 (self-cancellation)
• x ^ 0 = x (identity element)
• XOR is commutative and associative