Hamming Distance

Problem

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)

          

Code

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

    if x%2 != y%2:

        count+=1

    print(count)

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s