The Hamming Weight Problem is a common interview problem asked at FAANG companies Google. The goal of the problem is to calculate the Hamming weight of an array of integers. We’ll look at two ways of solving this problem — brute force and optimal. Let’s get started!

Hamming Weight Problem Statement

Calculate 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

{
"s": [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

Constraints:

• 1 <= input array length <= 10⁵
• 0 <= input array element < 2³²

We provided two solutions.

Let us denote size of input array s by n.

Hamming Weight Solution 1: Brute Force

Per the constraints, all the elements in the array can be stored in a 32-bit integer and hence, to calculate the number of set bits in an integer x, we can iterate on all these 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 the integer x.

Time Complexity

O(n).

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

Auxiliary Space Used

O(1).

We don’t store any data.

Space Complexity

O(n).

Space used for input: O(n).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(n) + O(1) + O(1) = O(n).

Code For Hamming Weight Solution 1: Brute Force

/*
* Asymptotic complexity in terms of size of \`s\` \`n\`:
* Time: O(n).
* Auxiliary space: O(1).
* Total space: O(n).
*/

int calculate_hamming_weight(vector<long long> &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;
}

Hamming Weight Solution 2: Optimal

Our main aim of the solution is to calculate the hamming distance of an integer x in constant time with some precomputation.

As the integer size is 32 bit as per the input constraints. So, we can divide the 32-bit integer x, into two 16-bits integers.

A = [31th , 30th , ……. , 17th, 16th]-bits

B = [ 15th , 14th, ………. , 1th , 0th]-bits

Let’s call the first part i.e. from [31th bit to 16th bit] as A and second part from [15th bit to 0th] bit as B. Also, note that both these integers A and B are 16-bit integers. Now, the total set bits in the integer x is equal to number of set bits in integer A + number of set bits in integer B and this is the key idea for this solution. Now let Sz be the number of all possible 16-bit integers. So, we precompute 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) tells 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].

Now, (5)base10 = (101)base2

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

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

As now, we have taken 0th bit of 5 under consideration and hence, 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 which is less than 5 and as we are iteratively computing dp states the resultant state dp[5 >> 1] would have already been computed. Hence, dp[5] = dp[2] + 1 i.e. last bit in 5 plus the number of set bits in 2.

Once, we have precomputed set bits individually for all 16-bit integers. We can answer calculate the number of set bits in a 32-bit integer by two lookups in the precomputed state values.

So, for an integer x we first divide it into A and B as explained above and then we do a lookup in our 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 count of the total number of set bits and hence, the hamming weight of the array.

Also, instead of dividing the array into 2 parts, we can divide it into 4 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, but will require 4 lookups and hence will double the previous time complexity. Though, the asymptotics remain the same.

Bonus take away – this is called as the Space-Time trade off.

Kindly, refer to the solution for implementation details.

Time Complexity

O(n + Sz).

Precomputing dp state for all 16 bit integers take a linear time O(2¹⁶) as explained above. To calculate the set bits in an integer x we are performing 2 iterations. Hence, for all n integers the time complexity become O(2 * n). Summing up the overall time complexity becomes O( 2 * n + Sz ) = O(n + Sz).

Auxiliary Space Used

O(Sz).

As, we are pre-computing set bits for all 16 bit integers and storing it. Hence the space complexity is O(Sz).

Space Complexity

O(n + Sz).

Space used for input: O(n).

Auxiliary space used: O(Sz).

Space used for output: O(1).

So, total space complexity: O(n) + O(Sz) + O(1) = O(n + Sz).

Code For Hamming Weight Solution 2: Optimal

/*
* Asymptotic complexity in terms of size of \`s\` \`n\` and total number of 16-bit integers \`Sz\` (= 2^16):
* Time: O(n + Sz).
* Auxiliary space: O(Sz).
* Total space: O(n + Sz).
*/

int calculate_hamming_weight(vector<long long> &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;
}

We hope that these solutions to the Hamming Weight problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.