Single Number III (LeetCode 260)

The problem

You get an array where every value appears exactly twice, except two values that each appear once. Return those two values (any order; this solution returns them sorted). Use O(n) time and O(1) extra space.

Input:  [1, 2, 1, 3, 2, 5]
Output: [3, 5]

1 and 2 appear twice; 3 and 5 appear once.

How to think about it

Start with brute force. A hash map or set of counts finds both in O(n) time but O(n) space. XOR-ing everything, as in Single Number, cancels the pairs but leaves a ^ b, not a and b separately.

The key insight: a ^ b tells you where a and b differ. Since a != b, a ^ b is non-zero, so it has at least one set bit. At that bit, one of a, b has a 1 and the other has a 0. Pick the lowest set bit: diff = xor & -xor (in two’s complement, -xor flips every bit above the lowest 1, so the AND keeps only that bit).

Split the array by that bit. Put every number with that bit set in group A, the rest in group B. a and b land in different groups. Each pair lands together in one group, because both copies have the same bit. So each group is now a plain Single Number problem: XOR group A to get one answer, and the other is xor ^ a.

Which pattern is this? Bit manipulation, XOR plus partitioning. The tell is “two elements appear once, the rest twice”. You never build the groups: just XOR the numbers with the bit set as you scan.

Approach

1. XOR every number to get xor = a ^ b.
2. Compute diff = xor & -xor, the lowest bit where a and b differ.
3. Scan again, XOR-ing only the numbers with x & diff set. The result is one of the singles, a.
4. The other is xor ^ a. Return both, sorted.

Solution

def single_number_iii(nums):
    xor = 0
    for x in nums:
        xor ^= x                  # pairs cancel, leaving a ^ b
    diff = xor & -xor          # a bit where a and b differ
    a = 0
    for x in nums:
        if x & diff:              # only one of a, b has this bit
            a ^= x
    return sorted([a, xor ^ a])
# single_number_iii([1,2,1,3,2,5]) -> [3,5]

Dry run

First pass: xor = 1^2^1^3^2^5 = 6 (110), so diff = 2 (010). Second pass:

a = 3 and xor ^ a = 6 ^ 3 = 5. The answer is [3, 5].

Complexity

• Time: O(n). Two passes.
• Space: O(1). A few integers.

Edge cases and pitfalls

• Zero is one of the answers ([0, 1]): 0 has no set bits, so it goes in group B, and xor ^ a recovers it. Returns [0, 1].
• Negative numbers work in Python: [-1, 0] returns [-1, 0]. In fixed-width languages, xor & -xor overflows when xor is the minimum int; use xor & ~(xor - 1) or an unsigned type.
• Any set bit works, not only the lowest. The lowest is just the cheapest to isolate.
• Return order. LeetCode accepts any order; sorting makes the output deterministic for tests.

Related problems

• Single Number (LeetCode 136): the one-single version this reduces to.
• Single Number II (LeetCode 137): one single among triples, with bit counting.
• Missing Number (LeetCode 268): XOR cancellation against a known range.