Total Hamming Distance solution and explanation
9 more videos on this problem
花花酱 LeetCode 477. Total Hamming Distance - 刷题找工作 EP132Hua Hua · 7:28 · 3K views
Leetcode 461/477 (Total) Hamming DistanceRen Zhang · 13:05 · 2K views
LC 477: Total Hamming Distance, Part 1Dinesh Kumar · 4:21 · 979 views
Leetcode [477] Total Hamming DistanceSDE Skills · 3:55 · 908 views
Explaining Leetcode #477 Total Hamming Distance (Medium)JTECH · 18:14 · 878 views
Leetcode 477. Total Hamming Distance (bit manipulation)LetsCode · 7:51 · 480 views
LC 477: Total Hamming distance, Part 2 (Code)Dinesh Kumar · 2:46 · 340 views
Bit Manipulation 12. Total Hamming Distance | AlgoMaster Sheet | Leetcode 477 |CS FOR ALL · 14:09 · 337 views
How I approach a new problem ? | 477. Total Hamming Distance (approach at end) | Leetcode ProblemPrince Mishra · 11:32 · 198 views
477 Total Hamming Distanceictbattle · 11:10 · 119 views
The problem
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 <= 1040 <= 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.
def hammingDistance(x, y):
xor = x ^ y
return bin(xor).count('1')
def totalHammingDistance(nums):
total_distance = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
total_distance += hammingDistance(nums[i], nums[j])
return total_distance
# Example usage
nums = [4, 14, 2]
print(totalHammingDistance(nums)) # Output: 6public class Solution {
public int hammingDistance(int x, int y) {
int xor = x ^ y, count = 0;
while (xor > 0) {
count += xor & 1;
xor >>= 1;
}
return count;
}
public int totalHammingDistance(int[] nums) {
int totalDistance = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
totalDistance += hammingDistance(nums[i], nums[j]);
}
}
return totalDistance;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {4, 14, 2};
System.out.println(sol.totalHammingDistance(nums)); // Output: 6
}
}#include <iostream>
#include <vector>
int hammingDistance(int x, int y) {
int xorValue = x ^ y, count = 0;
while (xorValue) {
count += xorValue & 1;
xorValue >>= 1;
}
return count;
}
int totalHammingDistance(std::vector<int>& nums) {
int totalDistance = 0, n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
totalDistance += hammingDistance(nums[i], nums[j]);
}
}
return totalDistance;
}
int main() {
std::vector<int> nums = {4, 14, 2};
std::cout << totalHammingDistance(nums) << std::endl; // Output: 6
return 0;
}function hammingDistance(x, y) {
let xor = x ^ y, count = 0;
while (xor > 0) {
count += xor & 1;
xor >>= 1;
}
return count;
}
function totalHammingDistance(nums) {
let totalDistance = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
totalDistance += hammingDistance(nums[i], nums[j]);
}
}
return totalDistance;
}
// Example
const nums = [4, 14, 2];
console.log(totalHammingDistance(nums)); // Output: 6#include <stdio.h>
int hammingDistance(int x, int y) {
int xor = x ^ y, dist = 0;
while (xor > 0) {
dist += xor & 1;
xor >>= 1;
}
return dist;
}
int totalHammingDistance(int* nums, int numsSize) {
int totalDist = 0;
for (int i = 0; i < numsSize - 1; i++) {
for (int j = i + 1; j < numsSize; j++) {
totalDist += hammingDistance(nums[i], nums[j]);
}
}
return totalDist;
}
int main() {
int nums[] = {4, 14, 2};
int result = totalHammingDistance(nums, 3);
printf("%d\n", result); // Output: 6
return 0;
}using System;
public class Solution {
public int HammingDistance(int x, int y) {
int xor = x ^ y, count = 0;
while (xor > 0) {
count += xor & 1;
xor >>= 1;
}
return count;
}
public int TotalHammingDistance(int[] nums) {
int totalDistance = 0;
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
totalDistance += HammingDistance(nums[i], nums[j]);
}
}
return totalDistance;
}
public static void Main() {
int[] nums = {4, 14, 2};
Solution sol = new Solution();
Console.WriteLine(sol.TotalHammingDistance(nums)); // Output: 6
}
}In Python, the hammingDistance function computes the XOR of two numbers and uses the bin().count('1') method to count 1s in the binary representation. The totalHammingDistance function calculates the sum of Hamming distances between all pairs.
Time Complexity: O(n^2 * k), assuming k is constant (32 bits).
Space Complexity: O(1)
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.
def totalHammingDistance(nums):
total_distance = 0
n = len(nums)
for i in range(32):
bit_count = sum((num >> i) & 1 for num in nums)
total_distance += bit_count * (n - bit_count)
return total_distance
# Example usage
nums = [4, 14, 2]
print(totalHammingDistance(nums)) # Output: 6public class Solution {
public int totalHammingDistance(int[] nums) {
int totalDistance = 0, n = nums.length;
for (int i = 0; i < 32; i++) {
int bitCount = 0;
for (int num : nums) {
bitCount += (num >> i) & 1;
}
totalDistance += bitCount * (n - bitCount);
}
return totalDistance;
}
public static void main(String[] args) {
int[] nums = {4, 14, 2};
Solution sol = new Solution();
System.out.println(sol.totalHammingDistance(nums)); // Output: 6
}
}#include <iostream>
#include <vector>
int totalHammingDistance(std::vector<int>& nums) {
int totalDistance = 0;
int n = nums.size();
for (int i = 0; i < 32; ++i) {
int bitCount = 0;
for (int num : nums) {
bitCount += (num >> i) & 1;
}
totalDistance += bitCount * (n - bitCount);
}
return totalDistance;
}
int main() {
std::vector<int> nums = {4, 14, 2};
std::cout << totalHammingDistance(nums) << std::endl; // Output: 6
return 0;
}function totalHammingDistance(nums) {
let totalDistance = 0, n = nums.length;
for (let i = 0; i < 32; i++) {
let bitCount = 0;
for (let num of nums) {
bitCount += (num >> i) & 1;
}
totalDistance += bitCount * (n - bitCount);
}
return totalDistance;
}
// Example
const nums = [4, 14, 2];
console.log(totalHammingDistance(nums)); // Output: 6#include <stdio.h>
int totalHammingDistance(int* nums, int numsSize) {
int totalDist = 0;
for (int i = 0; i < 32; i++) {
int bitCount = 0;
for (int j = 0; j < numsSize; j++) {
bitCount += (nums[j] >> i) & 1;
}
totalDist += bitCount * (numsSize - bitCount);
}
return totalDist;
}
int main() {
int nums[] = {4, 14, 2};
int result = totalHammingDistance(nums, 3);
printf("%d\n", result); // Output: 6
return 0;
}public class Solution {
public int TotalHammingDistance(int[] nums) {
int totalDistance = 0;
for (int i = 0; i < 32; i++) {
int bitCount = 0;
foreach (int num in nums) {
bitCount += (num >> i) & 1;
}
totalDistance += bitCount * (nums.Length - bitCount);
}
return totalDistance;
}
public static void Main() {
int[] nums = {4, 14, 2};
Solution sol = new Solution();
Console.WriteLine(sol.TotalHammingDistance(nums)); // Output: 6
}
}This Python implementation counts the number of set bits at each position over all numbers. It calculates the total Hamming distance by the contribution from each bit position using bit_count * (n - bit_count).
Time Complexity: O(n * k) where k is constant (32).
Space Complexity: O(1)
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).
function totalHammingDistance(nums: number[]): number {
let ans = 0;
for (let i = 0; i < 32; ++i) {
const a = nums.filter(x => (x >> i) & 1).length;
const b = nums.length - a;
ans += a * b;
}
return ans;
}func totalHammingDistance(nums []int) (ans int) {
for i := 0; i < 32; i++ {
a := 0
for _, x := range nums {
a += x >> i & 1
}
b := len(nums) - a
ans += a * b
}
return
}impl Solution {
pub fn total_hamming_distance(nums: Vec<i32>) -> i32 {
let mut ans = 0;
for i in 0..32 {
let mut a = 0;
for &x in nums.iter() {
a += (x >> i) & 1;
}
let b = (nums.len() as i32) - a;
ans += a * b;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Pairwise Calculation | Time Complexity: O(n^2 * k), assuming k is constant (32 bits). |
| Bit by Bit Calculation | Time Complexity: O(n * k) where k is constant (32). |
| Bit Manipulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Pairwise Calculation | O(n² * B) | O(1) | Small arrays or when demonstrating the direct XOR-based Hamming distance calculation |
| Bit-by-Bit Contribution Counting | O(n * 32) ≈ O(n) | O(1) | General case and interview settings where large input sizes require a linear-time solution |
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.