Total Hamming Distance
MediumArrayMathBit Manipulation
Description
Given an integer array nums, return the total Hamming distance between all pairs. Hamming distance is the number of bit positions where corresponding bits are different.
Examples
Input:
nums = [4,14,2]Output:
6Explanation:
Pairwise distances sum to 6.
Input:
nums = [1,3,5]Output:
4Explanation:
Binary representations: 1=001, 3=011, 5=101. Hamming distances: (1,3)=1 bit difference, (1,5)=2 bit differences, (3,5)=3 bit differences. Total: 1+2+3=6.
Input:
nums = [0,1,2,4]Output:
9Explanation:
Binary: 0=000, 1=001, 2=010, 4=100. Distances: (0,1)=1, (0,2)=1, (0,4)=1, (1,2)=2, (1,4)=2, (2,4)=2. Total: 1+1+1+2+2+2=8. Shows how powers of 2 create specific bit patterns.
Constraints
- •
1 ≤ nums.length ≤ 10⁴