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. Example: Input:
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.
Assuming we apply XOR among all numbers in
nums and get
res, we can dig out some info from
res: for each bit
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
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.
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 0
Therefore, we can either use
n&-n to get the rightmost set digit for