Total Hamming Distance LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Facebook
Bit ManipulationViews 2020

Problem Statement:

Total Hamming Distance LeetCode Solution:

Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Example 1:

Input:

 nums = [4,14,2]

Output:

 6

Explanation:

In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Example 2:

Input:

 nums = [4,14,4]

Output:

 4

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 109
  • The answer for the given input will fit in a 32-bit integer.

Approach

Idea

  1. The first solution that comes to our mind is to brute-force iterate through each pair, then sum all Integer.bitCount(x ^ y) .So This complexity O(N*N) gives TLE.
  2. Now, look into the efficient manner. The total Hamming distance is constructed bit by bit in this approach.
  3. For each bit position 1-32 in a 32-bit integer belonging to the array, we count the number of integers in the array which have that bit set.
  4. Then, if there are n integers in the array and k of them have a particular bit set and (n-k) do not, then that bit contributes n* (n-k) to the hamming distance.
  5. Because for each of the ‘k’ numbers, we have 1 of the (n-k) numbers, that have a different bit and the number of ways to select 1 from k and (n-k) numbers is kC1​∗n−kC1​=k⋅(n−k).
  6. For every bit, we will calculate how many are sets and how many are not sets. We will simply multiply both values for every bit position 1-32.
  7. To check whether the bit is set or not we can use left shift or right shift bit manipulation.
  8.  Look into the below code for a better understanding.

Code

Total Hamming Distance LeetCode C++ Solution

class Solution {
public:
    #define ll int
    int totalHammingDistance(vector<int>& nums) {
        ll i,j,n=nums.size();
        ll cnt=0;
         for(i=0;i<32;i++)
        {
            int one=0,zero=0;
            for(j=0;j<n;j++)
            {
                if((nums[j]&(1<<i))>0)
                {
                    one++;
                }
                else
                    zero++;
            }
            cnt+=one*zero;
            
        }
        return cnt;
    }
};

Total Hamming Distance LeetCode Java Solution

class Solution {
    public int totalHammingDistance(int[] nums) {
         int i,j,n=nums.length;
        int cnt=0;
        
        for(i=0;i<32;i++)
        {
            int one=0,zero=0;
            for(j=0;j<n;j++)
            {
                if((nums[j]&(1<<i))>0)
                {
                    one++;
                }
                else
                    zero++;
            }
            cnt+=one*zero;
            
        }
        return cnt;
    }
}

Complexity Analysis for Total Hamming Distance LeetCode Solution

Time Complexity

Time complexity is O(N*32) or simply say O(N). Where N is the size of the input array.

Space Complexity

Space complexity is O(1) as we not taking any extra space.

Translate »