Python implementation with negative numbers


  • 2
    P

    I wrote following code which performs well when input are all positive, but outputs a very big wrong answer if there is negative input:

    test case:

    a = [1,1,-3,1]
    O: 4294967293
    a = [1,2,3,2,2,1,1]
    O: 3

    I think this related to negative number binary representation in python. But I cannot figure out the details. Anybody can do me a favor? Many thanks!

    def singleNumber(self,A):
    	n = len(A)
    	if n==0:
    		return A[0]
    	else:
    		result = 0
    		for j in range(32):
    			mask = 1 << j  
    			sum = 0
    			for i in range(n):
    				if (A[i] >> j) & 1:
    					# bb = aa >> j
    					sum = sum + 1
    			output = sum%3
    			result = (output << j) | result
    		return result

  • 0
    B

    Getting the same error. I added a check to see if the number if positive or negative.
    If Positive, call this method;
    Otherwise, map as positive and then call this method.


  • 0
    P

    This is how you might convert an int to unsigned int in Python:

    a = A[i] & 0xffffffff
    if (a >> j) & 1:
    

    Though I wasn't able to find a Python solution that doesn't hit TLE. The closest I could get was this:

    def singleNumber2(self, A):
        digits = [0] * 32
        for a in A:
            n = a & 0xffffffff
            for i in range(32):
                digits[i] += n  & 1
                n >>=1
        res = 0
        for i in range(32):
            res <<=1
            res += digits[31 - i] % 3
        return res
    

    I translated it to Java and got it accepted


  • 2
    Z

    My solution:

    class Solution:
        # @param A, a list of integer
        # @return an integer
        def singleNumber(self, A):
            result = -0
            for i in range(32):
                bit = 0
                for n in A:
                    bit+=(n>>i)&1
                result |= (bit%3)<<i
            if result & 0x80000000:
                return -(result ^ 0xFFFFFFFF ) -1
            else:
                return result
    

    This is how I do the conversion:

        if result & 0x80000000:
            return -(result ^ 0xFFFFFFFF ) -1
        else:
            return result
    

  • 4
    C

    I end up handling the negative numbers separately:

    def singleNumber(self, A):
        ret = 0
        neg = sum(i < 0 for i in A)
        sign = -1 if neg % 3 else 1
        
        for i in range(32):
            val = sum((abs(num) >> i) & 1 for num in A) % 3
            ret += val << i
        return sign * ret

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.