The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Now your job is to find the total Hamming distance between all pairs of the given numbers.
Input: 4, 14, 2 Output: 6 Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). So the answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
xorof two bits is
1if they are not the same, and
xor of two numbers will give a bitwise representation of where the bits of two numbers differ. Such bit positions are represented by a
1 bit in the resultant. For example:
0010 1101 == 45\n ^ 0100 1010 == 74\n----------------\n 0110 0111\n ^^ ^^^ => 5 differing bits\n
Hence the numbers and have five differing bits. Thus the Hamming Distance between them is .\n
For each of the pairs of elements, simply apply bitwise
xor to them to find out a resultant representation which tells us the differing bits. Count the
1 bits to find the Hamming Distance for that pair of elements. Sum over all pairs to get the total Hamming Distance.
__builtin_popcount() method is an internal built-in function available in C (and hence by extension C++) which gives the count of
1 bits for an
int type argument. Being a low level built-in method, it is understandably faster than running a hand rolled loop.\nAs an alternative, you can iterate over all the bits of the number and count the
1 bits. Take a look at the code for Approach #2 for hints on how to achieve that.
Time complexity: .\n
xored, result in a resultant number which is bits long. Here is the largest value any of the elements can ever take.
1bits. In our case, since all elements are , the value is a small constant. Hence counting the
1bits takes place in nearly constant (i.e. ) time.
Space complexity: constant space.\n
Looping over all possible combinations of two element pairs, increases quadratically over the size of the input. If we could instead loop over the bits of the elements (which is constant), we could shave off an input dimension from our runtime complexity.\n
Say for any particular bit position, count the number of elements with this bit ON (i.e. this particular bit is
1). Let this count be . Hence the number of elements with this bit OFF (i.e.
0) is (in an element array).
Certainly unique pairs of elements exists where one element has this particular bit ON while the other element has this OFF (i.e. this particular bit differs for the two elements of this pair).\n
We can argue that every such pair contributes one unit to the Hamming Distance for this particular bit.\n
We know that the count of such unique pairs is for this particular bit. Hence Hamming Distance for this particular bit is .\n
For each of the bits that we can check, we can calculate a Hamming Distance pertaining to that bit. Taking sum over the Hamming Distances of all these bits, we get the total Hamming Distance.\n\n
NOTE: You can switch the order of the loops while counting
1 bits without affecting complexity. However it might give some performance changes due to locality of reference and the resultant cache hits/misses.
Time complexity: . Runtime performance is limited by the double loop where we are counting elements for particular bits. In our case, since all elements are , the value is a small constant. Thus the inner loop runs in nearly constant time.\n
Space complexity: extra space.\n
This question is a perfect example of how vectorized operations can result in small, elegant and good performance code. Take a look at this slick Python solution to this problem (by @StefanPochmann):\n\n
* operator turns the list of
32-bit wide binary strings returned by
map into individual arguments to the
zip method. The
zip method vectorizes the string arguments to create a list of vectors (each of which is a vector
b of particular bits from every element in the input array; There are
32 such vectors of size
len(nums) each, in this list ). Finally we use the same technique as Approach #2 to calculate the total Hamming Distance.
Analysis written by @babhishek21.\n