Compute the hamming distance of an array of integers using their binary representation


  • 1
    O

    The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different (https://en.wikipedia.org/wiki/Hamming_distance). In the case of integers, you have to use their binary representation as strings.
    For example:
    3 = "11"; 1 = "01"; HammingDistance(3,1) = 1;
    93 = "1011101"; 73 = "1001001"; HammingDistance(93, 73) = 2;
    You can observe that it's the number of bits set after an XOR operation between two integers. But doing the same operation for n integers is too slow. You have to observe that it's the sum of multiplication of number of bits set by number of bits unset for each i bit where 0<i<sizeof(int)

    Here is an O(n) solution in C#

    public int HammingDistance(int[] input)
    {
      // the result is the number of 1 bits x number of 0 bits
      int total = 0;
      if (input != null && input.Length > 1)
      {
        // Counts number of bits set per position
        int[] onebitscounter = new int[32];
        for (int i = 0; i < input.Length; ++i)
        {
          int j = 0;
          while (input[i] != 0)
          {
            if (input[i] % 2 == 1)
              onebitscounter[j] += 1;
            // shift one bit to the right
            input[i] = input[i] >> 1;
            ++j;
          }
        }
    
        for (int k = 0; k < 32; ++k)
        {
          total += onebitscounter[k] * (input.Length - onebitscounter[k]);
        }
      }
      return total;
    }

Log in to reply
 

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