# 477. Total Hamming Distance II

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given an integer array `nums`

, return *the sum of **Hamming distances** between all the pairs of the integers in* `nums`

.

**Example 1:**

**Input:** nums = [4,14,2]

**Output:** 6

**Explanation:** In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just

showing the four bits relevant in this case).

The answer will be:

HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

**Example 2:**

**Input:** nums = [4,14,4]

**Output:** 4

Approach 1:

*Naive approach:*

Check each pair of number and calculate their hamming distances . At the end return total hamming distance.

*Time: O(n²)*

*Space :O(1)*

Clearly this solution would lead to time limit exceeded.

`class Solution:`

def totalHammingDistance(self, nums: List[int]) -> int:

val=0

cnt=0

for i in range(len(nums)-1):

for j in range(i,len(nums)):

val=nums[i]^nums[j]

while(val):

cnt+=(val&1)

val>>=1

return(cnt)

Approach 2:

**More optimised solution**

Here each numbers can at max be 32 bits in binary form . So for each bit position starting from the rightmost bit position , we calculate total number of zeros and ones in that position and their product would give total hamming distance for that bit position for all numbers. This is continued for all bit position from right to left.

Finally Total hamming distance is returned

`class Solution:`

def totalHammingDistance(self, nums: List[int]) -> int:

total=0

for i in range(32):

ones,zeros,=0,0

for j in range(len(nums)):

if(nums[j]&1==1):

ones+=1

else:

zeros+=1

nums[j]>>=1

total+=ones*zeros

return total

*Time: O(N)*

*Space :O(1)*