Jobs

Interviews

Discussions

Hamming Distance

Easy

Asked by:

More companies

27 views

Topics:

Bit Manipulation

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

Given two integers x and y, return the Hamming distance between them.

Example 1:

Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
The above arrows point to positions where the corresponding bits are different.

Example 2:

Input: x = 3, y = 1
Output: 1

Constraints:

0 <= x, y <= 2³¹ - 1

Note: This question is the same as 2220: Minimum Bit Flips to Convert Number.

Try coding it in LeetCode

Hamming Distance

Easy

Asked by:

27 views

Topics:

Bit Manipulation

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

Given two integers x and y, return the Hamming distance between them.

Example 1:

Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
The above arrows point to positions where the corresponding bits are different.

Example 2:

Input: x = 3, y = 1
Output: 1

Constraints:

0 <= x, y <= 2³¹ - 1

Note: This question is the same as 2220: Minimum Bit Flips to Convert Number.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer inputs x and y?
Can x and y be negative integers?
Are x and y guaranteed to be integers, or could they be other data types?
Could x and y be equal to each other, and if so, what is the expected Hamming distance?
Should I optimize for any specific bit width representation (e.g., 32-bit, 64-bit) or can I assume the platform's default integer size?

Brute Force Solution

Approach

The Hamming distance problem asks us to find how many positions differ between two strings of equal length. The brute force approach directly compares each position in the strings to identify differences. This involves checking every single corresponding position one by one.

Here's how the algorithm would work step-by-step:

Take the first position in the first string.
Compare it with the character at the same position in the second string.
If the characters are different, mark it as a difference.
Move to the next position in both strings.
Again, compare the characters at these positions.
If they are different, mark it as another difference.
Continue this process, comparing characters at each position until you reach the end of both strings.
Count the total number of differences you've marked. This is the Hamming distance.

Code Implementation

def hamming_distance_brute_force(first_string, second_string):
    string_length = len(first_string)
    hamming_distance = 0

    # Iterate through each position in the strings.
    for index in range(string_length):

        #Check if the characters at current position differ.
        if first_string[index] != second_string[index]:
            hamming_distance += 1

    return hamming_distance

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the strings once, comparing characters at corresponding positions. The number of comparisons is directly proportional to the length of the strings, denoted as 'n'. Therefore, the time complexity is O(n), where 'n' is the length of the input strings, because each position is checked only once. The dominant operation is the single pass comparison of 'n' characters.

Space Complexity

O(1) – The provided plain English description of the Hamming distance algorithm iterates through two strings, comparing characters at each position. It only uses a counter to track the number of differences. No additional data structures like arrays, hash maps, or recursion are used. Therefore, the auxiliary space used is constant, regardless of the length of the input strings (N).

Optimal Solution

Approach

The Hamming distance measures the number of positions at which two pieces of data are different. The most efficient strategy is to determine how the numbers are different on a bit-by-bit basis, because at the fundamental level, computers see all data as a series of binary digits.

Here's how the algorithm would work step-by-step:

Think about how the numbers are represented as a series of 0s and 1s.
Combine the two numbers into one in a way that highlights where they differ. This is typically done with a special operation.
Count how many 1s are in the combined number. Each 1 represents a place where the original numbers had different bits.
The total count of 1s is the Hamming distance.

Code Implementation

def hammingDistance(integer_x, integer_y):
    # XOR operation highlights differing bits
    xor_result = integer_x ^ integer_y

    hamming_distance_count = 0

    # Count the number of set bits (1s)
    while xor_result:
        # This isolates the rightmost set bit
        xor_result &= (xor_result - 1)

        hamming_distance_count += 1

    return hamming_distance_count

Big(O) Analysis

Time Complexity

O(1) – The algorithm's time complexity depends on the number of bits needed to represent the input integers, which is a fixed size regardless of the integer's value. Combining the numbers with a bitwise XOR operation takes constant time. Counting the number of set bits also takes constant time since it depends on the fixed size of the data type (e.g., 32 bits for a 32-bit integer). Therefore, the number of operations does not grow with the input size, resulting in a constant time complexity of O(1).

Space Complexity

O(1) – The provided steps describe bitwise operations and counting. No auxiliary data structures, such as arrays, hash maps, or lists, are created to store intermediate results. The algorithm only manipulates the input numbers directly and uses a single counter to keep track of the number of differing bits. Therefore, the space used remains constant regardless of the input values, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
x and y are both 0	The Hamming distance is 0 since all bits are the same, so the algorithm should return 0.
x and y are the same number	The Hamming distance is 0 since all bits are the same, so the algorithm should return 0.
x is 0 and y is a large number	The algorithm correctly counts the set bits in y.
x is a large number and y is 0	The algorithm correctly counts the set bits in x.
x and y are both the maximum 32-bit integer (2^31 - 1)	Algorithm should work correctly without integer overflow issues.
x is the maximum 32-bit integer and y is its negative (-2^31)	Algorithm should correctly compute the Hamming distance by considering all bit positions.
x and y are very close in value (differ by only 1 or 2 bits)	The algorithm efficiently finds the small number of differing bits.
Integer overflow during XOR operation (if implemented using manual shifting)	Use bitwise operators (&, >>, ^) carefully to avoid integer overflow issues during intermediate calculations if not using XOR directly.

x and y are both 0

How to Handle:

The Hamming distance is 0 since all bits are the same, so the algorithm should return 0.

x and y are the same number

How to Handle:

The Hamming distance is 0 since all bits are the same, so the algorithm should return 0.

x is 0 and y is a large number

How to Handle:

The algorithm correctly counts the set bits in y.

x is a large number and y is 0

How to Handle:

The algorithm correctly counts the set bits in x.

x and y are both the maximum 32-bit integer (2^31 - 1)

How to Handle:

Algorithm should work correctly without integer overflow issues.

x is the maximum 32-bit integer and y is its negative (-2^31)

How to Handle:

Algorithm should correctly compute the Hamming distance by considering all bit positions.

x and y are very close in value (differ by only 1 or 2 bits)

How to Handle:

The algorithm efficiently finds the small number of differing bits.

Integer overflow during XOR operation (if implemented using manual shifting)

How to Handle:

Use bitwise operators (&, >>, ^) carefully to avoid integer overflow issues during intermediate calculations if not using XOR directly.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer inputs x and y?
Can x and y be negative integers?
Are x and y guaranteed to be integers, or could they be other data types?
Could x and y be equal to each other, and if so, what is the expected Hamming distance?
Should I optimize for any specific bit width representation (e.g., 32-bit, 64-bit) or can I assume the platform's default integer size?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first position in the first string.
Compare it with the character at the same position in the second string.
If the characters are different, mark it as a difference.
Move to the next position in both strings.
Again, compare the characters at these positions.
If they are different, mark it as another difference.
Continue this process, comparing characters at each position until you reach the end of both strings.
Count the total number of differences you've marked. This is the Hamming distance.

Code Implementation

def hamming_distance_brute_force(first_string, second_string):
    string_length = len(first_string)
    hamming_distance = 0

    # Iterate through each position in the strings.
    for index in range(string_length):

        #Check if the characters at current position differ.
        if first_string[index] != second_string[index]:
            hamming_distance += 1

    return hamming_distance

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Think about how the numbers are represented as a series of 0s and 1s.
Combine the two numbers into one in a way that highlights where they differ. This is typically done with a special operation.
Count how many 1s are in the combined number. Each 1 represents a place where the original numbers had different bits.
The total count of 1s is the Hamming distance.

Code Implementation

def hammingDistance(integer_x, integer_y):
    # XOR operation highlights differing bits
    xor_result = integer_x ^ integer_y

    hamming_distance_count = 0

    # Count the number of set bits (1s)
    while xor_result:
        # This isolates the rightmost set bit
        xor_result &= (xor_result - 1)

        hamming_distance_count += 1

    return hamming_distance_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
x and y are both 0	The Hamming distance is 0 since all bits are the same, so the algorithm should return 0.
x and y are the same number	The Hamming distance is 0 since all bits are the same, so the algorithm should return 0.
x is 0 and y is a large number	The algorithm correctly counts the set bits in y.
x is a large number and y is 0	The algorithm correctly counts the set bits in x.
x and y are both the maximum 32-bit integer (2^31 - 1)	Algorithm should work correctly without integer overflow issues.
x is the maximum 32-bit integer and y is its negative (-2^31)	Algorithm should correctly compute the Hamming distance by considering all bit positions.
x and y are very close in value (differ by only 1 or 2 bits)	The algorithm efficiently finds the small number of differing bits.
Integer overflow during XOR operation (if implemented using manual shifting)	Use bitwise operators (&, >>, ^) carefully to avoid integer overflow issues during intermediate calculations if not using XOR directly.

x and y are both 0

How to Handle:

The Hamming distance is 0 since all bits are the same, so the algorithm should return 0.

x and y are the same number

How to Handle:

The Hamming distance is 0 since all bits are the same, so the algorithm should return 0.

x is 0 and y is a large number

How to Handle:

The algorithm correctly counts the set bits in y.

x is a large number and y is 0

How to Handle:

The algorithm correctly counts the set bits in x.

x and y are both the maximum 32-bit integer (2^31 - 1)

How to Handle:

Algorithm should work correctly without integer overflow issues.

x is the maximum 32-bit integer and y is its negative (-2^31)

How to Handle:

Algorithm should correctly compute the Hamming distance by considering all bit positions.

x and y are very close in value (differ by only 1 or 2 bits)

How to Handle:

The algorithm efficiently finds the small number of differing bits.

Integer overflow during XOR operation (if implemented using manual shifting)

How to Handle:

Use bitwise operators (&, >>, ^) carefully to avoid integer overflow issues during intermediate calculations if not using XOR directly.