Hamming Distance


The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

1   (0 0 0 1)

4   (0 1 0 0)



def distanceFinder(self,x,y,count):

    if x%2 != y%2:



    if x/2 == 0 and y/2 == 0:

        return count

    return self.distanceFinder(int(x/2),int(y/2),count)

def hammingDistance(self, x, y):

    return self.distanceFinder(x,y,0)

Developer’s Notes

For this problem, I took a basic recursion approach and tested the distance by finding if then modulus of 2 is different. If it is different then I increment a counter. Once the numbers are 0 then it returns the counter. Since the algorithm uses recursion and depths by half each time the BigO looks to be O(log x). It is due to the fact that x and y are the same lengths.