Solution: Single Number II

Let's solve the Single Number II problem using the Bitwise Manipulation pattern.

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≤2 \leq arr.length ≤103\leq 10^3

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

Solution

The XOR operation is a bitwise operation that returns 11 if the two bits are different and 00 if they are the same. When we XOR an element with itself, we get 00 because the bits of the elements are identical. Therefore, if we XOR all pairs of duplicate elements in an array, we’ll get 00 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.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.