Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

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!

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.

```
{
"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

Constraints:

- 1 <= input array length <= 10
^{5} - 0 <= input array element < 2
^{32}

We provided two solutions.

Let us denote size of input array `s`

by `n`

.

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`

.

O(n).

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

O(1).

We don’t store any data.

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).

```
/*
* 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;
}
```

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.

O(n + Sz).

Precomputing dp state for all 16 bit integers take a linear time O(2^{16}) 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).

O(Sz).

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

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).

```
/*
* 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.

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

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!

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.

```
{
"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

Constraints:

- 1 <= input array length <= 10
^{5} - 0 <= input array element < 2
^{32}

We provided two solutions.

Let us denote size of input array `s`

by `n`

.

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`

.

O(n).

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

O(1).

We don’t store any data.

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).

```
/*
* 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;
}
```

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.

O(n + Sz).

Precomputing dp state for all 16 bit integers take a linear time O(2^{16}) 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).

O(Sz).

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

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).

```
/*
* 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.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart