Given an array of numbersnums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. Example: Input:[1,2,1,3,2,5]Output:[3,5]
Another bit operation problem after [Leetcode problems]136. Single Number and [Leetcode problems]137. Single Number II. Honestly you’ve got to be familiar with bit operations to come up with the solution in O(n) time complexity and O(1) space complexity. Let’s walk through the logic and see how does it work.
Logic
Assuming we apply XOR among all numbers in nums and get res, we can dig out some info from res: for each bit b in res, if b==0, it means the two unique numbers are the same on this bit; else if b==1, it means the two unique numbers differ here.
Using any of bit of 1 in res, we can divide nums into two groups: numbers with 0 on that bit and number with 1 on that bit. In this case, two unique numbers will be assigned into two groups and, since all others come as pairs, we can apply XOR in each group and the only unique one will remain.
Here’s a trick to find the rightmost set digit referred from @qeatzy in How to get position of right most set bit in C.
x: leading bits 1 all 0
~x: reversed leading bits 0 all 1
~x + 1 or -x: reversed leading bits 1 all 0
x & -x: all 0 1 all 0Therefore, we can either use n&~(n-1) or n&-n to get the rightmost set digit for n.
Code
