Skip to main content

477. Total Hamming Distance

medium

Sum the Hamming distance between every pair of numbers in an array. Brute force is O(n^2 * 32); the bit-column trick brings it down to O(32 * n).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

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

Examples

Example 1

Input
nums = [4,14,2]
Output
6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010. 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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

All-pairs Hamming distance directly is O(n^2). With n = 10^4 that's 10^8 — borderline TLE.

Hint 2

Flip your view: don't iterate pairs, iterate bit positions.

Hint 3

For each of the 32 bit positions, count how many numbers have a 1 there (call it k). The pairs that disagree at that bit are k * (n - k). Sum across bit positions.

Solution approach

Reveal approach

Bit-column counting. For each bit position b from 0 to 31, count ones = number of elements in nums with the b-th bit set. The pairs disagreeing at bit b are ones * (n - ones), and each such pair contributes 1 to the total. Sum across all 32 bit positions. The transformation is the trick: each pair contributes 1 per differing bit, and that's exactly what the bit-column sum captures. O(32n) ≈ O(n) time, O(1) space. Massive constant-factor win over O(n^2).

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • bit-manipulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Facebook
  • Amazon

Practice these live with InterviewChamp.AI

Drill Total Hamming Distance and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →