This article includes the code implementation in Python, a detailed explanation, and the complexity analysis for LeetCode - 260. Single Number III. Please hit the like button if you find this article is helpful to you. I will keep writing LeetCode solutions.

Explanation

In this question, we need to figure out the two numbers which appear only once. The first step is to xor all the numbers in the array, you can get a number that has at least a one-bit difference between the two numbers. Use the number from Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

The number 3 is 011 and the number 5 is 101 so it has a different bit at the second the 2nd and 3rd bit. Then we can use this to divide all the numbers into two groups.

Let say if we use the rightmost different bit between the number 3 and the number 5. The input array can be divided into two groups as below.

Group 1: [2, 3, 2] -> these numbers' 2nd bit are 1
Group 2: [1, 1, 5] -> these numbers' 2nd bit are 0

Finally, we can xor all the numbers within these two groups to get the number which appears only once in each group.

Group 1 after xor is [3]
Group 2 after xor is [5]

Code Implementation in Python

def singleNumber(self, nums: List[int]) -> List[int]:
    xor = 0 
    for num in nums: # xor all the number in the input array
        xor ^= num

    rightmost1Bit = 1

    # Find the rightmost different bit which returns 1 with & operation
    while xor & rightmost1Bit == 0: 
        rightmost1Bit <<= 1
    res = [0, 0]

    # Divide the number in the input array into two groups and do xor at the same time. 
    for num in nums: 
        # Use & operator to find the number with the same rightmost 1 bit. 
        if num & rightmost1Bit: 
            res[0] ^= num
        else:
            res[1] ^= num
    return res

Complexity Analysis

O(n) time | O(1) space - where n is the length of the input array