Single Number II

Question

Given 3*n + 1 numbers, every numbers occurs triple times except one, find it.

Thoughts

use an array to record every bit occurance, % 3, the result is the bit in that single number

对于java,只要建一个32位的array 而对于python来说，因为Python是弱类型语言，当int溢出时会自动转换为long，这样如果得到的结果res为负数，其32位二进制码首位为1，那么Python会自动转为long，也就是说int型的负数会转换为long型的正数。

参考

所以对于python的正负处理也要注意，可以先将所有的数都转换为正的，记录负数的个数，最后%3也就知道那个数是正的还是负的了

Solution

class Solution:
    """
    @param A : An integer array
    @return : An integer
    """
    def singleNumberII(self, A):
        # write your code here
        re = 0
        neg = 0
        for i in range(32):
            #sum of this bit occurance
            sum = 0
            for num in A:
                if num < 0:
                    neg += 1
                    num = num * -1
                #need to & 1 to clear other bits
                sum += (num >> i) & 1
            sum %= 3
            re += sum << i
        if neg % 3 > 0:
            re = re * -1
        return re