Python Explanation

  • 10

    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.


    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


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

  • 0

    @awice Took a while to understand the code, but its a brilliant strategy.

Log in to reply

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