Is Total Hamming Distance easy or hard?

Total Hamming Distance is generally classified as a Medium problem. The brute force solution is straightforward, but recognizing the per-bit contribution trick and reducing O(n²) comparisons to O(n) requires understanding of bit manipulation patterns.

Total Hamming Distance Python/Java solution

In Python or Java, implement the optimized solution by looping over 32 bit positions and counting set bits in the array. Multiply the number of ones and zeros for each bit and add the result to the total distance. This keeps the runtime linear with constant memory.

How to solve Total Hamming Distance in O(n)?

Iterate through each bit position from 0 to 31. For each bit, count how many numbers contain a 1 at that position and how many contain a 0. Multiply these counts to get the number of pairs contributing to the Hamming distance for that bit, then sum the contributions across all bits.

What is the best approach for Total Hamming Distance?

The best approach is the bit-by-bit counting method. For each of the 32 bit positions, count how many numbers have a 1 and how many have a 0. Each differing pair contributes one to the Hamming distance, so the contribution is ones × zeros. This produces an O(n) solution with constant extra space.

Is Total Hamming Distance asked at Google/Amazon/Meta?

Total Hamming Distance appears in interview preparation lists for companies like Google, Amazon, and Meta because it tests bit manipulation and optimization from quadratic to linear time. Variants involving XOR and bit counting are common interview patterns.

What data structure is used in Total Hamming Distance?

The problem primarily uses arrays and bit manipulation operations. The optimized solution iterates through the array multiple times while extracting bits using shift and mask operations such as (num >> bit) & 1.

What is the time complexity of Total Hamming Distance?

The optimal solution runs in O(n * 32) time, which simplifies to O(n) since integers have a fixed number of bits. The brute force approach that compares every pair takes O(n² * B), where B is the number of bits per integer.

Description Solution Video 7:28

477. Total Hamming Distance

Medium55.3% acceptance3 companies

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.

Asked at 3 companies

Apple Meta Bloomberg

Topics

7:28

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

477. Total Hamming Distance

Asked at 3 companies

Topics

Similar problems