136. Single NumberI, II, III

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution:

Single Number I:

xor: cancel out the same number

(268) Missing Number: find the missing number in an array of n elements Given nums=[0, 1, 3]return 2

xor the whole array with 1 to n, the result is the missing number.

Single Number II: Find the number appear one time and the other appear three times:

For an integer with 32 bits, we need to find which bit = 1 for the desire number. Since all the other number appeared three times, so that number of 1 at each 32 bit position should be to be divided by three. if not, the left 1 will be the desire number's 1.

Single Number III: Find the two number appeared only once.

using the same solution as Single Number I we can get a^b. Then how to use this value to separate a and b? For an integer with 32 bits, there must been at least one bit of the 32bits for a and b, where they're different. we can use the different bit to separate the array into two and find a and b from two different array. How to find the different bit? ----> all the ones in a^ b are the different bit between a and b. assume a^b = tmp, then the last bit they are different is tmp - (tmp & (tmp-1))