Python solution with detailed explanation


  • 0
    G

    Solution with discussion https://discuss.leetcode.com/topic/73553/python-solution-with-detailed-explanation

    Hamming Distance https://leetcode.com/problems/hamming-distance/

    Mask based linear time algorithm

    • Use a mask 1 and move it i times for each index. Use it to extract bit i for x and y and xor to update count.
    • Time complexity: O(32)
    class Solution(object):
        def hammingDistance(self, x, y):
            """
            :type x: int
            :type y: int
            :rtype: int
            """
            mask, cnt = 1, 0
            for i in range(31):
                if ((mask << i)&x) ^ ((mask << i)&y):
                    cnt += 1
            return cnt
    

    Using n&(n-1) trick

    • xor x and y.
    • n&(n-1) unsets the leftmost bit. Use it to count 1s.
    • Time complexity: O(hamming distance)
    class Solution(object):
        def hammingDistance(self, x, y):
            """
            :type x: int
            :type y: int
            :rtype: int
            """
            xor, cnt = x^y, 0
            while xor:
                cnt, xor = cnt+1, xor&(xor-1)
            return cnt
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.