SIngle Number II

Problem: Single Number II

Hash way to solve this problem is quite easy. The general idea is to use quick-search feature of hash table to update occurrence of numbers.

Code in Python:

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        numdict = {}
        for x in nums:
            if x in numdict:
                if numdict[x] == 1:
                    numdict[x] += 1
                elif numdict[x] == 2:
                    del numdict[x]
            else:
                numdict[x] = 1

        key, value = numdict.popitem()
        return int(key)

The difficulty lies in the bit manipulation method. To me, the general idea of bit manipulation is to accumulate sums of numbers appear once, numbers appear twice and numbers appear 3 times separately. At last we subtract the 3rd sum from 1st sum to get the result.

This impossible mission can be translated to bitwise accumulation. We accumulate bits appears to be 1 three times together and subtract that from accumulation of bits appeared to be 1 once to get the answer. To do so, we also need the accumulation of bits be 1 twice.

The detailed explanation can be found from Internet. Since it's impolite to copy others' words, I will only show my own code to this question for your understanding.

Code in Python:

def singleNumber1(self, nums):
        one, two, three = 0, 0, 0
        for x in nums:
            two |= one & x
            one ^= x
            three = two & one

            one = one & ~three
            two = two & ~three
        return one