hardBit ManipulationPure DSA~30 min
Sum of Pairwise Bit Differences Across an Array
Sum the Hamming distance over every pair of numbers in an array — the total count of differing bit positions across all pairs.
Problem
Given an integer array nums, return the sum of Hamming distances between all pairs of the numbers. The Hamming distance between two numbers is the count of bit positions where they differ.
Input
An integer array nums.
Output
An integer: the total pairwise Hamming distance.
Constraints
- 1 <= nums.length <= 10^4
- 0 <= nums[i] < 2^30
- The answer fits in a 64-bit integer.
Examples
Example 1
Input
nums = [4,14,2]
Output
6
Pairwise distances 2 + 2 + 2 sum to 6.
Example 2
Input
nums = [4,14,4]
Output
4
Only the pairs involving 14 differ.