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.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
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