Most efficient python 3 solution

programming
Tags: #<Tag:0x00007f242661acf0>

#1

class Solution:
# @param A : tuple of integers
# @return an integer
def hammingDistance(self, A):
l=[]

    for i in A:
        l.append('{:032b}'.format(i))
    c=0
        
    l=list(zip(*l))
    for i in l:
        a=i.count('0')
        b=i.count('1')
        c+=(2*a*b)
    return (c%1000000007)

#2

slightly improved

def hammingDistance(A):
    l = []
    for i in A:
        l.append('{:032b}'.format(i))

    c=0 
    l=list(zip(*l))
    for i in l:
        a=i.count('1')
        c+= a*(len(A)-a)

    return 2*c%1000000007

but you use O(n) additional space to store a copy of A in a different format


#3

O(1) space solution

        pos = {i : 0 for i in range(32)}
        
        for n in A:
            for i, bit in enumerate(bin(n)[-1:1:-1]):
                if bit == '1':
                    pos[i] += 1

            """
                another option:
                for i, bit in enumerate([n >> i & 1 for i in range(31,-1,-1)]):
                    pos[i] += bit
            """ 
                    
        ans = 2*sum([t*(len(A) - t) for t in pos.values()])            
            
        return ans % 1000000007

#4

How come you didn’t use a list and instead went for a dict.
32 items won’t make any actual difference but still, if you’re going for maximum efficiency you can use a list and avoid using pos.values() which would make a list first.

Also, you can store the length of the list A once and use that instead of calculating it again and again in a loop. Won’t make any real difference because it is just 32 elements but it is still good practice.

l = len(A)
pos = [0] * 32
for n in A:
    for i, bit in enumerate(bin(n)[-1:1:-1]):
        if bit == '1':
           pos[i] += 1
    return (2 * sum([t * (l - t) for t in pos])) % 1000000007

#5

Great solution! Loved it.


#6

Hey , I couldn’t completely understand why this works , and cant find anywhere where it might be explained well, could you guys explain/point me to a resource where the intuition is a bit more detailed, on why the solution actually works ?
Thanks