What is the Hamming distance?

The Hamming distance between two integers is the number of bit positions where their binary representations differ.

How do you calculate the Total Hamming Distance efficiently?

Instead of calculating pairwise Hamming distances directly, you can optimize by counting how often a particular bit is 1 in the array and using that to compute the total distance.

What is the time complexity of the optimized solution for the Total Hamming Distance problem?

The optimized solution has a time complexity of O(n * 32), where n is the length of the array and 32 is the maximum number of bits for any number.

What is the primary pattern used to solve the Total Hamming Distance problem?

The primary pattern is array manipulation combined with bitwise operations, allowing for efficient computation of Hamming distances.

How does GhostInterview help solve this problem?

GhostInterview provides solutions that focus on bit manipulation to reduce time complexity and optimize for larger input sizes, ensuring efficient problem-solving.

#477

Medium

auto_awesome数组·数学

LeetCode 题解工作台

汉明距离总和

两个整数的汉明距离指的是这两个数字的二进制数对应位不同的数量。给你一个整数数组 nums ，请你计算并返回 nums 中任意两个数之间汉明距离的总和。示例 1：输入： nums = [4,14,2] 输出： 6 解释：在二进制表示中，4 表示为 0100 ，14 表示为 1110 ，…

数组数学位运算

题目描述

两个整数的汉明距离指的是这两个数字的二进制数对应位不同的数量。

给你一个整数数组 nums，请你计算并返回 nums 中任意两个数之间 汉明距离的总和 。

示例 1：

输入：nums = [4,14,2]
输出：6
解释：在二进制表示中，4 表示为 0100 ，14 表示为 1110 ，2表示为 0010 。（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6

示例 2：

输入：nums = [4,14,4]
输出：4

提示：

1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁹
给定输入的对应答案符合 32-bit 整数范围

lightbulb

解题思路

方法一：位运算

我们在 $[0, 31]$ 的范围内枚举每一位，对于当前枚举的位 $i$ ，我们统计所有数字中的第 $i$ 位为 $1$ 的个数 $a$ ，那么这些数字中的第 $i$ 位为 $0$ 的个数就是 $b = n - a$ ，其中 $n$ 是数组的长度。这样的话，在第 $i$ 位上的汉明距离之和就是 $a \times b$ ，我们把所有的位的汉明距离相加即为答案。

时间复杂度 $O(n \times \log M)$ ，其中 $n$ 和 $M$ 分别是数组的长度和数组中的元素的最大值。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(32):
            a = sum(x >> i & 1 for x in nums)
            b = n - a
            ans += a * b
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate familiarity with bit manipulation and array traversal.
question_mark
Look for an understanding of time complexity optimization when discussing larger input sizes.
question_mark
Expect the candidate to recognize the inefficiencies of a brute force solution and propose an optimized approach.

warning

常见陷阱

外企场景

error
Misunderstanding the definition of Hamming distance and incorrectly comparing non-corresponding bits.
error
Failure to optimize the brute force solution, resulting in an inefficient approach for larger arrays.
error
Incorrect handling of edge cases, such as arrays with very small or very large values.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Calculate Hamming distance for a fixed number of integers instead of all pairs.
arrow_right_alt
Modify the problem to calculate the Hamming distance between a given set of numbers and a target number.
arrow_right_alt
Optimize for extremely large arrays, aiming for constant time solutions based on preprocessed bit counts.

help

常见问题

外企场景

继续练习

#268 丢失的数字 #782 变为棋盘 #805 数组的均值分割