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
0 Comments