477. Total Hamming Distance

Time: O(30n)

Space: O(1)

Intuition

For each bit position, count how many numbers have 0 vs 1. Every pair of (0,1) contributes 1 to Hamming distance. Total contribution = ones * zeros.

Algorithm

1For each of 32 bit positions:
2Count c = numbers with bit set.
3Add c * (n - c) to answer.

Example Walkthrough

Input: nums=[4,14,2]

1.Bit 1: [0,1,1]→ones=2, zeros=1 → 2.
2.Bit 2: [1,1,0]→ones=2, zeros=1 → 2.
3.Bit 3: [0,1,0]→ones=1, zeros=2 → 2.
4.Total=6.

Output: 6

Common Pitfalls

•This is O(32n) vs O(n²) naive pairwise.

477.cs

// Approach: For each of the 30 bit positions, count ones and zeros across
// all numbers; contribute ones×zeros pairs to the total distance.
// Time: O(30n) Space: O(1)

public class Solution
{
    public int TotalHammingDistance(int[] nums)
    {
        const int kMaxBit = 30;
        int ans = 0;

        for (int i = 0; i < kMaxBit; ++i)
        {
            int mask = 1 << i;
            int ones = nums.Count(num => (num & mask) > 0);
            int zeros = nums.Length - ones;
            ans += ones * zeros;
        }

        return ans;
    }
}

Was this solution helpful?