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.
This is a variant of 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.
classSolution {
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;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution {
publicintsumHammingDistancesBrute(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;
}
}
1
2
3
4
5
6
7
8
9
10
classSolution:
defsumHammingDistancesBrute(self, arr: list[int]) -> int:
n, ans = len(arr), 0for i in range(n):
for j in range(n):
x = arr[i] ^ arr[j]
while x:
ans +=1 x &= x -1return ans
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)).
classSolution {
public:int cntBits(vector<int>&A) {
constint 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;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution {
publicintcntBits(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;
}
}
1
2
3
4
5
6
7
8
9
10
from typing import List
classSolution:
defcntBits(self, A: List[int]) -> int:
MOD =10**9+7 n = len(A)
ans =0for i in range(32):
cnt = sum((x >> i) &1for x in A)
ans = (ans +2* cnt * (n - cnt)) % MOD
return ans