278. Total Bit Distance
A lab archives n calibration codes, each stored as a non-negative integer. The bit distance between two codes is the number of binary positions at which they differ. Given the array nums, return the sum of the bit distances over every pair of indices i < j. Equal values at different indices are separate items and still form a pair (their distance is 0).
Every value is at most 10^9 and there are at most 3000 of them, so the total always fits in a signed 32-bit integer. Looking at all pairs one by one is too slow for the largest inputs; aim for roughly 30 passes over the array, O(n) time with a small constant, and O(1) extra space.
Example 1
- Input:
- nums = [9,14,3]
- Output:
- 8
- Explanation:
Summing the bit distances of all 3 pairs gives 8.
Example 2
- Input:
- nums = [40,40,7,0]
- Output:
- 17
- Explanation:
Summing the bit distances of all 6 pairs gives 17.
Example 3
- Input:
- nums = [1000000000,0]
- Output:
- 13
- Explanation:
Summing the bit distances of all 1 pairs gives 13.
Constraints
1 ≤ nums.length ≤ 3000
0 ≤ nums[i] ≤ 109
The answer fits in a signed 32-bit integer (at most about 6.8 * 107).
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(30 n)
- Space
- O(1)