# II. LeetCode questions

## 1. Single Number

• Diagram:
`a^a = 0a^0 = aa^b^a = (a^a)^b = 0^b = ba^b^c^a^c = (a^a)^(c^c)^b = 0^b = b`
• Code:
`# Time O(N) Space O(1)def singleNumber(self, nums: List[int]) -> int:    output = 0    for num in nums:        output ^= numreturn output`

## 2. Single Number II

• Diagram:
`Solution 1, using dictionay, time O(N) space O(N)Solution 2. using sort, time O(NlogN) space O(1)Solution 3. Using set, time O(N) space O(N)a+a+a+b+b+b+c+c = 3a+3b+2cSolution 4. using bitwise XOR, time O(N) space O(1)a XOR a = 0,0 XOR a = aa XOR a XOR a XOR b XOR b XOR b XOR c XOR c =  a XOR b XOR c`
• Code:
`#Time O(N) Space O(1)def singleNumber(self, nums: List[int]) -> int:            seen_once = 0    seen_twice = 0    for num in nums:        seen_once = seen_once ^ num & ~seen_twice        seen_twice = seen_twice ^ num & ~seen_once    return seen_once`

## 3. Simple Number III

• Diagram:
`a XOR b, a or b, but not botha XOR 0 = aa XOR a = 0a⊕b⊕a=(a⊕a)⊕b=0⊕b=ba XOR b XOR a XOR c = 0 XOR b XOR c = b XOR cx & (-x) to isolate the rightmost 1-bit. x & (-x) keep the rightmost 1-bit and to set all the other bits to 0Brain Kernighan's algorithm a & (a-1), turn off the rightmost 1-bit`
• Code:
`    # Time O(N) Space O(1)    def singleNumber(self, nums: List[int]) -> List[int]:                  if not nums: return []            a_xor_b = 0        for num in nums:            a_xor_b ^= num                    rightmost_1_bit = a_xor_b & (- a_xor_b)                a = 0        for num in nums:            if num & rightmost_1_bit:                a ^= num        return [a, a_xor_b ^ a]`

## 4. Power of two

a. Solution I, using a&(-a), to get the rightmost 1-bit

• Diagram:
`a&(-a), to get the rightmost 1-bit                    -a = 4 =       0000 0100~4 =          1111 1011-4 = ~4+1 =   1111 11004&(-4) =      0000 0100                    _                     pow(2,0) = 1 =  0000 0001pow(2,1) = 2 =  0000 0010pow(2,2) = 4 =  0000 0100pow(2,3) = 8 =  0000 1000pow(2,4) = 16 = 0001 0000if we get the rightmost 1-bit of above number, then we just get the number itselfso, if a & (a-1) == a, then a is power of two`
• Code:
`# Time O(1) Space O(1)def isPowerOfTwo(self, n: int) -> bool:    if not n or n < 1: return False    return n == n & (-n)`

Solution II, using Brain Kernighan’s algorithm, to turn off the rightmost bit of 1

• Diagram:
`Brain Kernighan's algorithm, to turn off the rightmost bit of 1                         -a = 4 --->         0000 0100a-1 = 3 --->       0000 0011a&(a-1) = 4&3 ---> 0000 0000                         -pow(2,0) = 1 =  0000 0001pow(2,1) = 2 =  0000 0010pow(2,2) = 4 =  0000 0100pow(2,3) = 8 =  0000 1000pow(2,4) = 16 = 0001 0000if we turn off the rightmost bit of above number, then we got 0000 0000so, if a & (a-1) == 0, then a is power of two`
• Code:
`#Time O(1) Space O(1)def isPowerOfTwo(self, n: int) -> bool:            if not n or n<1: return False    return n & (n-1)  == 0`

## More from Jing Dong

Software Engineer