Solution: Single Number II

Statement

Given a non-empty array arr, in which exactly two elements appear once, and all the other elements appear twice, return the two elements that appeared only once.

Note: The result can be returned in any order. The solution should use only constant extra space.

Constraints:

• $2 \leq$ arr.length $\leq 10^3$

• $−2^{31} \leq$ arr[i] $\leq 2^{31}-1$

Solution

The XOR operation is a bitwise operation that returns $1$ if the two bits are different and $0$ if they are the same. When we XOR an element with itself, we get $0$ because the bits of the elements are identical. Therefore, if we XOR all pairs of duplicate elements in an array, we’ll get $0$ because each duplicate pair cancels out. Then, if we XOR the remaining elements, the two unique numbers, we’ll get a result with at least one set bit (1-bit).

We can use any set bit of the result as a way to differentiate between the two unique numbers. In our algorithm, we will use the rightmost set bit. By checking if each element has this set bit or not in the corresponding position, we can consider the array into two groups. One group contains elements with the corresponding set bit, and the other contains elements without it. This allows us to separate the two unique numbers from each other.

Let's look into the algorithm and see how it works.