I don’t understand why sum of hamming distance of all pair of elements equals 2XY, Can anyone help me understand this with an example?
It’s basic P&C.
No. of ways of selecting num with set bit = x
No. of ways of selecting num with unset bit = y
No. of ways of arranging two numbers = 2
Answer = x * y * 2
Let X = the set of integers with 1 bit in position k.
Let Y = the set of integers with 0 bit in position k.
Considering only position k, the hamming distance between elements of set X is 0 and similarly for Y.
The hamming distance between an element of X and an element of Y is 1.
For each element in X, there are |Y| elements that can be paired with it to get a hamming distance of 1. So the sum of the hamming distances is |X| x |Y|.
For each element in Y, there are |X| elements that can be paired with it to get a hamming distance of 1. So the sum of the hamming distances is |Y| x |X|.
The total sum of hamming distances is 2 x |X| x |Y|.