Python Explanation


  • 8

    Notice the total hamming distance is the sum of the total hamming distance for each of the i-th bits separately.

    So, let's consider the i-th column, which consists of numbers chosen from {0, 1}. The total hamming distance would be the number of pairs of numbers that are different. That is,

    Total hamming distance for the i-th bit =
    (the number of zeros in the i-th position) *
    (the number of ones in the i-th position).

    We then add all of these together to get our answer.

    Code:

    bits = [ [0,0] for _ in xrange(32) ]
    for x in A:
      for i in xrange(32):
        bits[i][x%2] += 1
        x /= 2
    return sum( x*y for x,y in bits )
    

  • 1

    Could replace

      for i in xrange(32):
        bits[i][x%2] += 1
    

    with

      for bit in bits:
        bit[x%2] += 1

Log in to reply
 

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