Total Hamming Distance
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
6In binary representation, 4 is 0100, 14 is 1110, and 2 is 0010, so HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Example 2
Input
nums = [4,14,4]Output
4The pairwise Hamming distances among [4, 14, 4] sum to 4.
Constraints
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 10^9
- The answer for the given input will fit in a 32-bit integer.