About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career

Hamming Weight Problem

Calculate the Hamming weight of an array of integers. Hamming weight of an integer is defined as the number of set bits in its binary representation. Hamming weight of an array is a sum of Hamming weights of all numbers in it.

Example‍:

Input: [1, 2, 3]

Output: 4

Binary representation of 1 is “1”; one set bit.

Binary representation of 2 is “10”; one set bit.

Binary representation of 3 is “11”; two set bits.

1 + 1 + 2 = 4

‍‍Notes‍:

Input Parameters: The function has one parameter — an array of 64-bit integers

Output: The function returns an integer

Constraints:

  • 1 <= n <= 10^5
  • 0 <= s[i] < 2^32, where 0 <= i < n

Solution 1: Brute Force (brute_force_solution)

As per the constraints, all the elements in the array can be stored in a 32-bit integer. Hence, to calculate the number of set bits in an integer x, we can iterate on all 32 bits of the corresponding integer and keep a count of the number of set bits.

We repeat the same process for all integers in the given input array s and keep the count of total set bits in all integers. To optimize the solution, we can break traversal over the bits once we encounter the MSB (most significant bit/ leftmost set bit) in integer x.

Time Complexity:

O(n), where n is the number of elements in the given input array

For every integer in the array, we iterate over 32 bits (constant number of repetitions).

Auxiliary Space Used:

O(1)

We don’t store any data.

Space Complexity:

O(n)


// -------- START --------

int calculateHammingWeight(vector &s)
{
    // stores total number of set bits in all elements
    int totalSetBits = 0;
    // max number of bits in an integer (input constraint)
    int maxNumberOfBits = 32;
    int N = s.size();
    for (int i = 0; i < N; i++)
    {
        // iterate over all bits of s[i]
        for (int j = 0; j < maxNumberOfBits; j++)
        {
            // if jth bit is set increment totalSetBits
            if (s[i] & (1LL << j))
                totalSetBits++;
        }
    }
    // return final count of set bits
    return totalSetBits;
}
// -------- END --------
	

Solution 2: Optimal (optimal_solution)

Our aim is to calculate the Hamming distance of an integer x in constant time with some pre-computation. The integer size is 32 bit as per the input constraints. So, we can divide the 32-bit integer x into two 16-bit integers. 

[31st, 30th, ..., 17th, 16th] [15th, 14th, ..., 1st, 0th]

Let’s call the first part A and the second part B. Both these integers, A and B, are 16-bit integers. Now, the total set bits in the integer x is equal to the number of set bits in integer A + the number of set bits in integer B —  this is the key idea for this solution. 

Now, let Sz be the number of all possible 16-bit integers. So, we pre-compute the number of set bits for all Sz integers and store it in memory. We can compute the set bits for all Sz integers in linear time. Let’s say dp[i] denotes the number of set bits in integer i. So, we can compute dp[i] using the below state relation:

dp[i] = dp[i >> 1] + (i&1)

In the above relation, (i&1) shows if the 0th bit is set in the binary representation of the integer i. To illustrate the above relation, consider the calculation of dp[5]:

(5)base10 = (101)base2

So, dp[5] = dp[5 >> 1] + 5&1

Here, 5&1 is 1 as the 0th bit is set in the binary representation of 5.

We considered the 0th bit of 5, so now, we can right shift the binary representation of 5 by 1 to omit the 0th bit and then calculate the number of set bits in the resulting integer. Also, as right shifting 5 by 1 will result in an integer that is less than 5, and as we are iteratively computing dp states, the resultant state dp[5>>1] would have already been calculated. 

Hence, dp[5] = dp[2] + 1, i.e., last bit in 5 plus the number of set bits in 2.

Once we have pre-computed set bits individually for all 16-bit integers, we can calculate the number of set bits in a 32-bit integer using two lookups in the pre-computed state values.

So, for an integer x, we first divide it into A and B as explained above, and then we lookup dp[A] and dp[B] to get the set bits in the integer x. We repeat the same process for all integers in the array s and keep a count of the total number of set bits, i.e., the hamming weight of the array.

‍Also, instead of dividing the array into two parts, we can divide it into four integers, each of size 8 bits, and proceed the same way as we did in the above explanation. This will reduce the space complexity significantly. However, it will require four lookups, and hence, will double the previous time complexity. The asymptotics will remain the same. 

This is called the Space-Time trade-off.

Time Complexity:

O(n + Sz), where n is the number of elements in the given array s, and Sz is the number of all possible 16-bit integers, i.e., 2^16.

Pre-computing dp state for all 16-bit integers takes linear time O(2^16), as explained above. To calculate the set bits in an integer x, we perform two iterations. Hence, for all n integers, the time complexity becomes O(2*n). Add them up, and the overall time complexity becomes O( 2*n + Sz ) →  O(n + Sz).

Auxiliary Space Used:

O(Sz), where Sz is the number of all possible 16-bit integers, i.e., 2^16.

We pre-compute set bits for all 16-bit integers and store them. Hence, the space complexity is O(Sz).

Space Complexity:

O(n + Sz), where n is the number of elements in the given array s, and Sz is the number of all possible 16-bit integers, i.e., 2^16.

Storing input takes O(n). The auxiliary space used is O(Sz). Hence, the total complexity is O(n) + O(Sz) → O(n + Sz).


// -------- START --------

int calculateHammingWeight(vector &s)
{
    // size of mem dp table
    int sz = 1 << 16;
    // number of elements in s
    int N = s.size();
    // stores set bits in integers
    int memo[sz];
    // 0 set bits in integer 0
    memo[0] = 0;
    // using dp-state relation to populate
    // all dp states
    for (int i = 1; i < sz; i++)
    {
        memo[i] = memo[i >> 1] + (i & 1);
    }
    // total set bits in all N elements of s
    int totalSetBits = 0;
    // bit mask = (1<<16) - 1 = (1111111111111111) in binary
    int bitMask = sz - 1;
    // iterate over all elements in array
    for (int i = 0; i < N; i++)
    {
        // add set bits from (0th to 15th) bits position
        totalSetBits += memo[s[i] & bitMask];
        // shift s[i] 16 positions to right
        s[i] = s[i] >> 16;
        // again add set bits from (0th to 15th) bits position
        totalSetBits += memo[s[i] & bitMask];
    }
    return totalSetBits;
}
// -------- END --------
	


Attend our Free Webinar on How to Nail Your Next Technical Interview

Recommended Posts

All Posts