Jobs

Interviews

Discussions

Total Hamming Distance

Medium

Asked by:

43 views

Topics:

ArraysBit Manipulation

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

Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.

Example 1:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Example 2:

Input: nums = [4,14,4]
Output: 4

Constraints:

1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁹
The answer for the given input will fit in a 32-bit integer.

Try coding it in LeetCode

Total Hamming Distance

Medium

Asked by:

43 views

Topics:

ArraysBit Manipulation

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

Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.

Example 1:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Example 2:

Input: nums = [4,14,4]
Output: 4

Constraints:

1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁹
The answer for the given input will fit in a 32-bit integer.

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 is the range of values for the integers within the input array?
Can the input array be empty or null?
Are duplicate numbers allowed in the input array, and if so, should they be included in the Hamming distance calculation?
Is the order in which I calculate the Hamming distance between pairs important, or can I calculate them in any order?
Can you provide a few example inputs and their corresponding expected outputs to confirm my understanding of the problem?

Brute Force Solution

Approach

To find the total Hamming distance using brute force, we're essentially comparing every number in the set with every other number. We carefully count the differences between their binary representations and sum these counts to find the total distance.

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

Take the first number in the set.
Compare it to the second number, noting how many corresponding digits are different in their binary representations.
Add this count to our running total.
Compare the first number to the third number, and again add the difference count to the running total.
Continue comparing the first number to all the other numbers, updating the running total each time.
Now, move to the second number and compare it to the third, fourth, and all remaining numbers, adding the difference counts.
Repeat this process, comparing each number to all the numbers that come after it in the set.
The final running total will be the total Hamming distance for the entire set of numbers.

Code Implementation

def total_hamming_distance_brute_force(numbers):
    total_distance = 0
    list_length = len(numbers)

    for i in range(list_length):
        for j in range(i + 1, list_length):
            # Iterate through the remaining numbers

            first_number = numbers[i]
            second_number = numbers[j]
            xor_result = first_number ^ second_number

            hamming_distance = 0
            # Count the set bits in XOR result to get the hamming distance
            while xor_result:
                hamming_distance += xor_result & 1
                xor_result >>= 1

            total_distance += hamming_distance

    return total_distance

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach compares each number in the input array of size n with every other number. Specifically, the first number is compared with n-1 other numbers, the second number is compared with n-2 other numbers, and so on. This results in a nested-loop like structure where the total number of comparisons approximates n * (n-1) / 2. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The provided brute force approach calculates the Hamming distance by iterating through pairs of numbers in the input. It only requires a few integer variables: one or two for loop indices, and another to accumulate the running total of Hamming distances. The memory used by these variables does not scale with the input size N (where N is the number of integers in the input). Thus, the auxiliary space complexity is constant.

Optimal Solution

Approach

The key to efficiently calculating the total Hamming distance lies in focusing on individual bit positions across all numbers. Instead of comparing every number with every other number directly, we analyze each bit position separately to count the number of pairs with differing bits. This drastically reduces the computational effort.

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

Consider each bit position (e.g., the rightmost bit, the second bit from the right, etc.) individually.
For each bit position, count how many numbers have a '0' in that position and how many numbers have a '1' in that position.
Multiply the count of '0's by the count of '1's for that bit position. This gives you the number of pairs where that specific bit differs.
Add up the results from all the bit positions. This sum is the total Hamming distance.

Code Implementation

def total_hamming_distance(numbers):
    total_distance = 0
    list_length = len(numbers)

    # Iterate through each bit position (0 to 31 for 32-bit integers)
    for bit_position in range(32):
        count_zeros = 0

        # Count numbers with a '0' at the current bit position
        for number in numbers:
            if (number >> bit_position) & 1 == 0:
                count_zeros += 1

        # Calculates pairs with differing bits at this position.
        count_ones = list_length - count_zeros
        total_distance += count_zeros * count_ones

    return total_distance

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each bit position of the numbers. The number of bit positions is constant (up to 32 for integers, or a fixed size). For each bit position, we iterate through all n numbers in the input array to count the number of 0s and 1s at that position. Since the number of bit positions is constant, the dominant factor is the iteration through the n numbers. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm iterates through the bit positions of the numbers and counts the number of 0s and 1s at each position. These counts are stored in constant space variables. No additional data structures that scale with the input size N (the number of numbers) are used, meaning auxiliary space remains constant regardless of input size. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array	Return 0, as there are no pairs to calculate Hamming distance for.
Array with a single element	Return 0, as a single element cannot form a pair.
Array with all elements being the same number	The Hamming distance will be 0 for all pairs, so the sum should remain 0, which our algorithm will correctly produce.
Large input array (performance concern)	Bit manipulation avoids nested loops, giving O(n*k) where n is array size and k is the number of bits in each number (typically 32), so performance is linear and scalable.
Input numbers with a wide range of values (potential for integer overflow when calculating total distance)	Use a 64-bit integer (long) to store the total Hamming distance to prevent overflow.
Negative numbers in the input array	The bit manipulation approach still works correctly with negative numbers as they are represented in two's complement.
Array containing a mix of small and very large numbers	The algorithm correctly compares all bits regardless of the magnitude of the numbers.
Array where all numbers have a single bit set in different positions (e.g., 1, 2, 4, 8)	Each pair will have a Hamming distance of 2, so the total should be `n * (n - 1)`, which our algorithm will compute.

Empty input array

How to Handle:

Return 0, as there are no pairs to calculate Hamming distance for.

Array with a single element

How to Handle:

Return 0, as a single element cannot form a pair.

Array with all elements being the same number

How to Handle:

The Hamming distance will be 0 for all pairs, so the sum should remain 0, which our algorithm will correctly produce.

Large input array (performance concern)

How to Handle:

Bit manipulation avoids nested loops, giving O(n*k) where n is array size and k is the number of bits in each number (typically 32), so performance is linear and scalable.

Input numbers with a wide range of values (potential for integer overflow when calculating total distance)

How to Handle:

Use a 64-bit integer (long) to store the total Hamming distance to prevent overflow.

Negative numbers in the input array

How to Handle:

The bit manipulation approach still works correctly with negative numbers as they are represented in two's complement.

Array containing a mix of small and very large numbers

How to Handle:

The algorithm correctly compares all bits regardless of the magnitude of the numbers.

Array where all numbers have a single bit set in different positions (e.g., 1, 2, 4, 8)

How to Handle:

Each pair will have a Hamming distance of 2, so the total should be `n * (n - 1)`, which our algorithm will compute.

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 is the range of values for the integers within the input array?
Can the input array be empty or null?
Are duplicate numbers allowed in the input array, and if so, should they be included in the Hamming distance calculation?
Is the order in which I calculate the Hamming distance between pairs important, or can I calculate them in any order?
Can you provide a few example inputs and their corresponding expected outputs to confirm my understanding of the problem?

Brute Force Solution

Approach

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

Take the first number in the set.
Compare it to the second number, noting how many corresponding digits are different in their binary representations.
Add this count to our running total.
Compare the first number to the third number, and again add the difference count to the running total.
Continue comparing the first number to all the other numbers, updating the running total each time.
Now, move to the second number and compare it to the third, fourth, and all remaining numbers, adding the difference counts.
Repeat this process, comparing each number to all the numbers that come after it in the set.
The final running total will be the total Hamming distance for the entire set of numbers.

Code Implementation

def total_hamming_distance_brute_force(numbers):
    total_distance = 0
    list_length = len(numbers)

    for i in range(list_length):
        for j in range(i + 1, list_length):
            # Iterate through the remaining numbers

            first_number = numbers[i]
            second_number = numbers[j]
            xor_result = first_number ^ second_number

            hamming_distance = 0
            # Count the set bits in XOR result to get the hamming distance
            while xor_result:
                hamming_distance += xor_result & 1
                xor_result >>= 1

            total_distance += hamming_distance

    return total_distance

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Consider each bit position (e.g., the rightmost bit, the second bit from the right, etc.) individually.
For each bit position, count how many numbers have a '0' in that position and how many numbers have a '1' in that position.
Multiply the count of '0's by the count of '1's for that bit position. This gives you the number of pairs where that specific bit differs.
Add up the results from all the bit positions. This sum is the total Hamming distance.

Code Implementation

def total_hamming_distance(numbers):
    total_distance = 0
    list_length = len(numbers)

    # Iterate through each bit position (0 to 31 for 32-bit integers)
    for bit_position in range(32):
        count_zeros = 0

        # Count numbers with a '0' at the current bit position
        for number in numbers:
            if (number >> bit_position) & 1 == 0:
                count_zeros += 1

        # Calculates pairs with differing bits at this position.
        count_ones = list_length - count_zeros
        total_distance += count_zeros * count_ones

    return total_distance

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0, as there are no pairs to calculate Hamming distance for.
Array with a single element	Return 0, as a single element cannot form a pair.
Array with all elements being the same number	The Hamming distance will be 0 for all pairs, so the sum should remain 0, which our algorithm will correctly produce.
Large input array (performance concern)	Bit manipulation avoids nested loops, giving O(n*k) where n is array size and k is the number of bits in each number (typically 32), so performance is linear and scalable.
Input numbers with a wide range of values (potential for integer overflow when calculating total distance)	Use a 64-bit integer (long) to store the total Hamming distance to prevent overflow.
Negative numbers in the input array	The bit manipulation approach still works correctly with negative numbers as they are represented in two's complement.
Array containing a mix of small and very large numbers	The algorithm correctly compares all bits regardless of the magnitude of the numbers.
Array where all numbers have a single bit set in different positions (e.g., 1, 2, 4, 8)	Each pair will have a Hamming distance of 2, so the total should be `n * (n - 1)`, which our algorithm will compute.

Empty input array

How to Handle:

Return 0, as there are no pairs to calculate Hamming distance for.

Array with a single element

How to Handle:

Return 0, as a single element cannot form a pair.

Array with all elements being the same number

How to Handle:

The Hamming distance will be 0 for all pairs, so the sum should remain 0, which our algorithm will correctly produce.

Large input array (performance concern)

How to Handle:

Bit manipulation avoids nested loops, giving O(n*k) where n is array size and k is the number of bits in each number (typically 32), so performance is linear and scalable.

Input numbers with a wide range of values (potential for integer overflow when calculating total distance)

How to Handle:

Use a 64-bit integer (long) to store the total Hamming distance to prevent overflow.

Negative numbers in the input array

How to Handle:

The bit manipulation approach still works correctly with negative numbers as they are represented in two's complement.

Array containing a mix of small and very large numbers

How to Handle:

The algorithm correctly compares all bits regardless of the magnitude of the numbers.

Array where all numbers have a single bit set in different positions (e.g., 1, 2, 4, 8)

How to Handle:

Each pair will have a Hamming distance of 2, so the total should be `n * (n - 1)`, which our algorithm will compute.