# Python implementation with negative numbers

• 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):
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``````

• 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.

• 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

• 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
``````

• 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``````

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