I wrote following code which performs well when input are all positive, but outputs a very big wrong answer if there is negative input:
a = [1,1,-3,1]
a = [1,2,3,2,2,1,1]
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 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
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 =  * 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
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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.