Sum of Pairwise Hamming Distances

Problem

We define f(X, Y) as the number of different corresponding bits in the binary representation of X and Y. For example, f(2, 7) = 2, since the binary representation of 2 and 7 are 010 and 111, respectively. The first and the third bit differ, so f(2, 7) = 2.

You are given an array of N positive integers, A1, A2,..., AN. Find sum of f(Ai, Aj) for all pairs (i, j) such that 1 ≤ i, j ≤ N. Return the answer modulo 10^9+7.

OR

Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given an array A of N non-negative integers, find the sum of hamming distances of all pairs of integers in the array. Return the answer modulo 10^9+7.

Examples

Example 1

Input: [1, 3, 5]
Output: 8
Explanation:
f(1, 1) + f(1, 3) + f(1, 5) +
f(3, 1) + f(3, 3) + f(3, 5) +
f(5, 1) + f(5, 3) + f(5, 5) =
0 + 1 + 1 + 1 + 0 + 2 + 1 + 2 + 0 = 8

Example 2

Input: [2, 4, 6]
Output: 8
Explanation:
f(2,2)=0, f(2,4)=2, f(2,6)=1
f(4,2)=2, f(4,4)=0, f(4,6)=1
f(6,2)=1, f(6,4)=1, f(6,6)=0
Sum = 0+2+1+2+0+1+1+1+0 = 8

Constraints

• 1 ≤ N ≤ 10^5
• 0 ≤ Ai ≤ 2^31 - 1

Notes

• This is a variant of [Total Hamming Distance](total-hamming-distance). The only difference is that this problem asks for all ordered pairs (including (i, i)), while LeetCode 477 asks for unordered pairs (i < j). The answer to this problem is exactly twice the LeetCode answer.

Solution

Method 1– Brute Force (Inefficient)

Intuition

Directly compute the Hamming distance for every ordered pair using XOR and count set bits.

Approach

1. For each pair (i, j), compute arr[i] ^ arr[j].
2. Count the number of set bits in the result (the Hamming distance).
3. Sum for all pairs.

Code

C++

class Solution {
public:
	int sumHammingDistancesBrute(vector<int>& arr) {
		int n = arr.size(), ans = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				int x = arr[i] ^ arr[j];
				while (x) {
					ans++;
					x &= x - 1;
				}
			}
		}
		return ans;
	}
};

Java

class Solution {
	public int sumHammingDistancesBrute(int[] arr) {
		int n = arr.length, ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int x = arr[i] ^ arr[j];
				while (x > 0) {
					ans++;
					x &= x - 1;
				}
			}
		}
		return ans;
	}
}

Python

class Solution:
	def sumHammingDistancesBrute(self, arr: list[int]) -> int:
		n, ans = len(arr), 0
		for i in range(n):
			for j in range(n):
				x = arr[i] ^ arr[j]
				while x:
					ans += 1
					x &= x - 1
		return ans

Complexity

• ⏰ Time complexity: O(n^2 * 32) — For each pair, we count set bits (up to 32 per pair).
• 🧺 Space complexity: O(1) — Only a few variables are used.

Method 2 – Bitwise Counting

Intuition

For each bit position, count how many numbers have a 1 and how many have a 0. Each such pair contributes 1 to the Hamming distance for every (i, j) pair where the bits differ. Since the sum is over all ordered pairs, each such pair is counted twice (once for (i, j) and once for (j, i)).

Approach

1. For each bit position from 0 to 31:
   • Count the number of elements with a 1 at that bit (cnt).
   • The number of elements with a 0 at that bit is (N - cnt).
   • The number of ordered pairs with different bits at this position is cnt × (N - cnt) × 2.
2. Sum this over all bit positions and return the result modulo 10^9+7.

Code

C++

class Solution {
public:
	int cntBits(vector<int> &A) {
		const int MOD = 1e9+7;
		long ans = 0;
		int n = A.size();
		for (int i = 0; i < 32; ++i) {
			int cnt = 0;
			for (int x : A) {
				if (x & (1 << i)) cnt++;
			}
			ans = (ans + 2L * cnt * (n - cnt)) % MOD;
		}
		return (int)ans;
	}
};

Java

class Solution {
	public int cntBits(int[] A) {
		int MOD = 1000000007;
		long ans = 0;
		int n = A.length;
		for (int i = 0; i < 32; i++) {
			int cnt = 0;
			for (int x : A) {
				if ((x & (1 << i)) != 0) cnt++;
			}
			ans = (ans + 2L * cnt * (n - cnt)) % MOD;
		}
		return (int)ans;
	}
}

Python

from typing import List
class Solution:
	def cntBits(self, A: List[int]) -> int:
		MOD = 10**9 + 7
		n = len(A)
		ans = 0
		for i in range(32):
			cnt = sum((x >> i) & 1 for x in A)
			ans = (ans + 2 * cnt * (n - cnt)) % MOD
		return ans

Complexity

• ⏰ Time complexity: O(N * 32) — We check each bit of each number.
• 🧺 Space complexity: O(1) — Only a few counters are used, regardless of input size.