leetcode[Single Number III].
Given an array of numbers
nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
nums = [1, 2, 1, 3, 2, 5], return
Solution. Since there are only 2 numbers which appears 1 time, other number appears 2 times. Let assume the number which appears 1 time are a and b. When we do xor operation on each element in nums, we get result of xorNum = a xor b.
Now, let’s get the first 1 in the xorNum counting fro right. We can do xorNum & (-xorNum). This skill is used in Indexed Binary Tree.
Let’s loop each num in nums for another round. We can divide num in 2 groups. One group has num & xorNum == 0, another group has num & xorNum != 0. In this way, we can get the 2 results.
check my code on github: link