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.
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  Group 2 after xor is 
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 ^= num else: res ^= num return res
O(n) time | O(1) space - where n is the length of the input array