Skip to main content
Talentd

Total Hamming Distance - Solution & Explanation

MediumArrayMathBit Manipulation16 min readAsked at: Apple, Meta, Bloomberg
Practice this problem

Problem Statement

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 <= 104
  • 0 <= nums[i] <= 109
  • The answer for the given input will fit in a 32-bit integer.

Approach Overview

Problem Overview: Given an integer array nums, compute the sum of Hamming distances for every pair of numbers. The Hamming distance between two integers is the number of bit positions where their binary representations differ.

This problem mixes array iteration with bit manipulation. A direct pairwise comparison works but becomes slow as the array grows. The key observation: Hamming distance is determined independently at each bit position.

Approach 1: Naive Pairwise Calculation (O(n² * B) time, O(1) space)

The straightforward approach checks every pair of numbers in the array. For each pair (i, j), compute the Hamming distance using XOR: x ^ y. The number of set bits in the result tells you how many positions differ. Use a loop or built-in popcount operation to count set bits. Accumulate the distance for all pairs.

This method relies only on simple math and bit operations, making it easy to understand and implement. However, it requires comparing n(n-1)/2 pairs, which quickly becomes expensive for large arrays. With n = 10^4, the quadratic growth makes it impractical. Still useful for verifying correctness or when input sizes are small.

Approach 2: Bit-by-Bit Contribution (O(n * 32) time, O(1) space)

The optimal solution flips the perspective. Instead of examining pairs, analyze each bit position independently. For a given bit index b, count how many numbers have that bit set (ones) and how many do not (zeros). Every pair consisting of one number with bit 1 and one with bit 0 contributes exactly one to the Hamming distance.

The number of such pairs is ones * zeros. Add this value to the total for that bit. Repeat for all 32 bit positions in a standard integer. Each iteration scans the array once and checks the bit using (num >> b) & 1. This converts the quadratic pairwise computation into a linear scan multiplied by the number of bits.

This works because bit positions contribute independently to the Hamming distance. Instead of evaluating every pair, you count how many pairs differ at each position in aggregate. The result is a time complexity of O(n * 32), which simplifies to O(n) for fixed-width integers.

Recommended for interviews: Interviewers expect the bit-by-bit counting approach. The brute-force pairwise method demonstrates understanding of XOR and Hamming distance, but the optimized solution shows you can recognize independent bit contributions and reduce quadratic work to linear time. Most accepted production solutions use the bit counting technique.

Approach 1: Naive Pairwise Calculation

This approach involves calculating the Hamming distance for each pair of numbers by comparing their binary representations. This naive method checks each bit position from the least significant bit to the most significant bit for each pair.

This C code defines a function hammingDistance that calculates the Hamming distance between two integers by XORing them and counting the number of 1s in the result. The totalHammingDistance function calculates the sum of Hamming distances for every pair in the array nums.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2 * k) where n is the number of numbers and k is the number of bits per integer (32).
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Bit by Bit Calculation

For each bit position, count how many numbers have that bit set. The number of pairs from two sets, one having the bit set and the other not, can be computed directly. This reduces the complexity significantly.

This C code iterates through each bit position from 0 to 31. bitCount keeps track of how many numbers have the current bit set. The Hamming distance contribution of this bit is given by bitCount * (numsSize - bitCount).

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * k) where n is the array size and k is 32 (number of bits).
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Bit Manipulation

We enumerate each bit in the range [0, 31]. For the current enumerated bit i, we count the number of numbers where the i-th bit is 1, denoted as a. Therefore, the number of numbers where the i-th bit is 0 is b = n - a, where n is the length of the array. In this way, the sum of the Hamming distance on the i-th bit is a times b. We add the Hamming distances of all bits to get the answer.

The time complexity is O(n times log M), where n and M are the length of the array and the maximum value in the array, respectively. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Naive Pairwise Calculation

Time Complexity: O(n^2 * k) where n is the number of numbers and k is the number of bits per integer (32).
Space Complexity: O(1)

Bit by Bit Calculation

Time Complexity: O(n * k) where n is the array size and k is 32 (number of bits).
Space Complexity: O(1)

Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Pairwise CalculationO(n² * B)O(1)Small arrays or when demonstrating the direct XOR-based Hamming distance calculation
Bit-by-Bit Contribution CountingO(n * 32) ≈ O(n)O(1)General case and interview settings where large input sizes require a linear-time solution

Video Solution

花花酱 LeetCode 477. Total Hamming Distance - 刷题找工作 EP132 • Hua Hua • 3,948 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Total Hamming Distance with our built-in code editor and test cases.

Practice on FleetCode
Previous

Hamming Distance

Next

Sum of Digit Differences of All Pairs