Total Hamming Distance
Advanced
The Hamming distance of two numbers is the number of bit positions where they differ. Return the sum of the Hamming distances over all pairs (i, j) with i < j.
For [4, 14, 2] (binary 0100, 1110, 0010) the answer is 6.
The starter code checks every pair. It is correct but too slow for long lists.
Examples
Example 1
Input:
total_hamming_distance([4, 14, 2])
Output:
6
Example 2
Input:
total_hamming_distance([4, 14, 4])
Output:
4
Constraints
1 <= len(nums) <= 500000 <= nums[i] < 2**30
Theory
Go to TheoryKeywords
dsa-sheetbit-manipulationbit-patterns
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.