arcbjorn

thoughtbook

Sunday, March 5, 2023

Total hamming distance

Leetcode 477 problem.

Go

  • Time complexity: O(n)O(n) - n is a length of a number array
  • Auxiliary space: O(1)O(1) - constant amount of space
func totalHammingDistance(nums []int) int {
    sum := 0
    length := len(nums)

    for i := 0; i < 32; i++ {
        oneFrequency := 0

        for i := range nums {
            oneFrequency = oneFrequency + nums[i] & 1
            nums[i] = nums[i] >> 1
        }

        sum = sum + oneFrequency * (length - oneFrequency)
    }

    return sum
}
Creative Commons Licence