Total Bit Differences Across Pairs
Problem
A network team compares device fingerprints stored as non-negative integers below 2^30. The difference between two fingerprints is the number of bit positions where they differ. Given a list of fingerprints, return the sum of the differences over every unordered pair. The list has up to 10,000 values, so XOR-ing every pair is too slow.
Examples
Input: nums = [4, 14, 2]
Output: 6
Why: 4 vs 14 differ in 2 bits, 4 vs 2 in 2, 14 vs 2 in 2Input: nums = [4, 14, 4]
Output: 4Input: nums = [7]
Output: 0
Why: edge case, one value makes no pairsHints
0 / 3
Counting the differing bits of one pair is a popcount of a ^ b, but there are n² / 2 pairs. Try turning the sum around: instead of looping over pairs, loop over bit positions.
Fix one bit position. A pair contributes 1 at that position exactly when one value has the bit on and the other has it off.
For each of the 30 positions, count the values with that bit on, say c. The number of mixed pairs there is c * (n - c). Add that up over all positions.
Solution
The total over all pairs can be summed one bit position at a time, because each pair's difference is just the count of positions where it disagrees. At a given position, a pair disagrees exactly when one value has a 1 and the other a 0, so with c ones among n values there are c * (n - c) disagreeing pairs, and no pair ever needs to be looked at on its own. That makes 30 passes of n values each, so time is O(30 · n) = O(n), and extra space is O(1).
def total_bit_differences(nums):
n, total = len(nums), 0
for bit in range(30):
ones = sum((x >> bit) & 1 for x in nums) # values with this bit on
total += ones * (n - ones) # each on/off pair differs here
return total
print(total_bit_differences([4, 14, 2])) # -> 6
print(total_bit_differences([4, 14, 4])) # -> 4
print(total_bit_differences([7])) # -> 0Stuck on the idea rather than the code? Counting Set Bits covers it.