Marc Lester Tan

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.