LeetCode 260 · Bits · Math

Single Number III, explained with a picture

Two odd socks separated by one switch.

Bits · Math
▶ Watch it step by step

The problem

Exactly two numbers appear once and all others appear twice. Find the two single numbers.

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

Picture it

Picture socks again, now with two loners. XOR of everything leaves a ^ b. Any switch that is on there is a position where a and b differ, so it splits all the socks into two piles, each containing one loner. XOR each pile separately.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

XOR all, pick a set bit, partition, XOR each group. O(n), O(1).

Python solution

def single_number(nums):
    xor = 0
    for x in nums:
        xor ^= x                   # = a ^ b
    low = xor & -xor               # a switch where a and b differ
    a = b = 0
    for x in nums:
        if x & low:
            a ^= x
        else:
            b ^= x
    return [a, b]

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.