 Register for our webinar

### How to Nail your next Technical Interview

1 hour 1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name  Step 1  Step 2
Congratulations!
You have registered for our webinar Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone  Step 1  Step 2 Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.  ## You may be missing out on a 66.5% salary hike* ### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.  ## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.  # Hamming Weight Problem

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 <= 105
• 0 <= input array element < 232

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
}
``````

# 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`.

Now, `(5)base10 = (101)base2`

So, `dp = 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 = dp + 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(216) 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;
// 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
// shift s[i] 16 positions to right
s[i] = s[i] >> 16;
// again add set bits from (0th to 15th) bits position
}
}
``````

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:

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

# Hamming Weight Problem

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 <= 105
• 0 <= input array element < 232

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
}
``````

# 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`.

Now, `(5)base10 = (101)base2`

So, `dp = 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 = dp + 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(216) 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;
// 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
// shift s[i] 16 positions to right
s[i] = s[i] >> 16;
// again add set bits from (0th to 15th) bits position
}
}
``````

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:

## Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve. Hosted By
Ryan Valles
Founder, Interview Kickstart Accelerate your Interview prep with Tier-1 tech instructors 360° courses that have helped 14,000+ tech professionals 100% money-back guarantee*

All Posts