Quoestion:Click Here

Approach:

we know that XOR operation return 1 when both bits are different,So we use it in finding hamming distance.

Example: x = 1,y = 4 if we perform XOR operation on this we get 0 1 0 1 
             
Output:No of 1's in XOR result

So if we count No of 1's in XOR result then it will be the Hamming distance.

There are many methods to count no of 1's in a binary number out of these most optimized method is Brian Kernighan's Algorithm



Brian Kernighan's Algorithm:
Step1:Intialize integer variable,distance
Step2:while number !=0
        ---Turn-off the rightmost 1 bit by performing below                 operation
               --num = num&(num-1)
        ---increment distance
Step3:return distance

Optimization:Rather than performing iterations for all the bits,we reduced it to only the small number of bits.

Time Complexity:O(1)
Space Complexity:O(1)

Python Code:

#Brian Kernighan's Algorithm
class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        num = x^y
        if num==0:
            return 0
        dist = 0
        while True:
            num = num & (num-1)
            dist+=1
            if num==0:
                return dist

Python One Liner:

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return bin(x^y).count('1')

Python Naive Approach:

class Solution(object):
    def hammingDistance(self, x, y):
        x = [i for i in str(bin(x))]
        x = x[2:]
        y = [i for i in str(bin(y))]
        y = y[2:]
        diff = abs(len(x)-len(y))
        if len(x) > len(y):
            for i in range(diff):
                y.insert(i,'0')
        else:
            for i in range(diff):
                x.insert(i,'0')
        count = 0
        for i in range(len(x)):
            if x[i]==y[i]:
                continue
            else:
                count+=1
        return count