[Leetcode]260. 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.
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.

Bits equals to 1 could be used as a flag.

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.

Divide the number into two groups regarding the flag.

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 0

Therefore, we can either use n&~(n-1) or n&-n to get the rightmost set digit for n.

Code

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments