My initial solution to this medium leetcode problem uses Kernighan’s way to calculate the number of 1’s in a binary:

fun hammingDistance(x: Int, y: Int): Int {
// using Kernighan's way
var ctr = 0
var v = x xor y
while(v != 0) {
v = v and v - 1
ctr++
}

return ctr
}


This works fine for small set of numbers but for our problem, it exceeded the time limit because I have to go through all the possible combinations and for each combination, I have to run through another loop to count the number of bits (Kernighan’s way). After my “research” :D, I could’ve just used Integer.bitCount which is way faster.

After replacing the function above with Integer.bitCount, the final code looks like:

class Solution {
fun totalHammingDistance(nums: IntArray): Int {
var sum = 0
val hamming: (Int, Int) -> Int = { x, y -> Integer.bitCount(x xor y)}

for(index in 0 until nums.size - 1){
var subIndex = index + 1
while(subIndex < nums.size){
sum += hamming(nums[index], nums[subIndex])
subIndex++
}
}

return sum
}
}


The code just simply goes through all the possible combinations of numbers and computing each pair’s hamming distance. All the computed distances will be summed-up altogether which will become our final answer.

Runtime: 3396 ms, faster than 18.18% of Kotlin online submissions for Total Hamming Distance.
Memory Usage: 41.3 MB, less than 100.00% of Kotlin online submissions for Total Hamming Distance.


PS: Just in case you’re curious what Integer.bitCount uses internally:

/**
530:    * Return the number of bits set in x.
531:    * @param x value to examine
532:    * @since 1.5
533:    */
534:   public static int bitCount(int x)
535:   {
536:     // Successively collapse alternating bit groups into a sum.
537:     x = ((x >> 1) & 0x55555555) + (x & 0x55555555);
538:     x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
539:     x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
540:     x = ((x >> 8) & 0x00ff00ff) + (x & 0x00ff00ff);
541:     return ((x >> 16) & 0x0000ffff) + (x & 0x0000ffff);
542:   }


Just freakin’ too difficult to understand what this code does so I’ll leave it to the gods.