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

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