Leetcode 137: Single Number II

 

Code

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0

        for i in xrange(32):
            sum = 0
            for n in nums:
                # right shift in Python is unsigned
                # i.e., leftmost is filled with 0
                sum += (abs(n) >> i) & 1
            sum = sum % 3
            if sum != 0:
                ans = ans | (1 << i)
        
        negsign = 0
        for n in nums:
           if n < 0:
               negsign += 1
        negsign = negsign % 3
            
        if negsign != 0 :
            return -ans
        else:
            return ans

 

 

 

Idea

Although there is a convoluted algorithm using bit operation to solve this problem, I feel it is impossible to come up with that during an interview. 

 

My current code borrows the idea from https://discuss.leetcode.com/topic/43166/java-o-n-easy-to-understand-solution-easily-extended-to-any-times-of-occurance. The idea is as follows: 

suppose an integer is 32 bit. For each bit position, count how many numbers in nums are non-zero on that bit and store the count in sum.  When sum % 3 != 0, you know the exceptional number has 1 on that bit. (The prerequisite is that the exceptional number appears k times in nums where k % 3 != 0. This is the condition that the question does not specify right now but it did in the previous version.)

 

Integers in Python are not  implemented as fixed-size bits. The right shift in Python is unsigned (the leftmost position is filled with 0). Therefore, we need to count separately whether the exceptional number is negative or positive. (line 19-23)