Given an integer array arr[], return the sum of Hamming distances between all the pairs of the integers in arr.
The Hamming distance between two integers is the number of bit positions at which the corresponding bits are different.
Note: The answer is guaranteed to fit within a 32-bit integer.
Examples:
Input: arr[] = [1, 14]
Output: 4
Explanation: Binary representations of 1 is 0001, 14 is 1110. The answer will be:
hammingDist(1, 14) = 4.Input: arr[] = [4, 14, 4, 14]
Output: 8
Explanation: Binary representations of 4 is 0100, 14 is 1110. The answer will be:
hammingDist(4, 14) + hammingDist(4, 4) + hammingDist(4, 14) + hammingDist(14, 4) + hammingDist(14, 14) + hammingDist(4, 14) = 2 + 0 + 2 + 2 + 0 + 2 = 8.
Try it on GfG Practice
Table of Content
[Naive Approach] - Checking Each Pair - O(n^2) Time and O(1) Space
Iterate over all pairs using nested loops and compute the Hamming distance by comparing their bits. For each bit position, increment the count if the bits differ. Sum all such counts to obtain the total Hamming distance across all pairs.
- Initialize a variable count to store the total Hamming distance.
- Use two loops to iterate over all unique pairs (i, j) such that j > i.
- For each pair, loop through all bit positions from 0 to 30.
- Check if the k-th bit of both numbers is different. If yes, then increment count.
- Return count
#include <iostream>
#include <vector>
using namespace std;
int totHammingDist(vector<int>& arr) {
int count = 0;
int n = arr.size();
// Loop through all unique pairs (i, j)
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// For each bit position from 0 to 30
for (int k = 0; k < 31; k++) {
// If bit k is set in arr[i] and not in arr[j]
if ((arr[i] & (1 << k)) && !(arr[j] & (1 << k))) {
count++;
}
// If bit k is not set in arr[i] and is set in arr[j]
else if (!(arr[i] & (1 << k)) && (arr[j] & (1 << k))) {
count++;
}
}
}
}
return count;
}
int main() {
vector<int> arr = {4, 14, 4, 14};
int ans = totHammingDist(arr);
cout << ans << endl;
return 0;
}
import java.util.*;
public class GfG {
static int totHammingDist(int[] arr) {
int count = 0;
int n = arr.length;
// Loop through all unique pairs (i, j)
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// For each bit position from 0 to 30
for (int k = 0; k < 31; k++) {
// If bit k is set in arr[i] and not in arr[j]
if (((arr[i] & (1 << k)) != 0) &&
((arr[j] & (1 << k)) == 0)) {
count++;
}
// If bit k is not set in arr[i] and is set in arr[j]
else if (((arr[i] & (1 << k)) == 0) &&
((arr[j] & (1 << k)) != 0)) {
count++;
}
}
}
}
return count;
}
public static void main(String[] args) {
int[] arr = {4, 14, 4, 14};
int ans = totHammingDist(arr);
System.out.println(ans);
}
}
def totHammingDist(arr):
count = 0
n = len(arr)
# Loop through all unique pairs (i, j)
for i in range(n):
for j in range(i + 1, n):
# For each bit position from 0 to 30
for k in range(31):
# If bit k is set in arr[i] and not in arr[j]
if (arr[i] & (1 << k)) and not (arr[j] & (1 << k)):
count += 1
# If bit k is not set in arr[i] and is set in arr[j]
elif not (arr[i] & (1 << k)) and (arr[j] & (1 << k)):
count += 1
return count
if __name__ == "__main__":
arr = [4, 14, 4, 14]
ans = totHammingDist(arr)
print(ans)
using System;
class GfG {
static int totHammingDist(int[] arr) {
int count = 0;
int n = arr.Length;
// Loop through all unique pairs (i, j)
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// For each bit position from 0 to 30
for (int k = 0; k < 31; k++) {
// If bit k is set in arr[i] and not in arr[j]
if (((arr[i] & (1 << k)) != 0) &&
((arr[j] & (1 << k)) == 0)) {
count++;
}
// If bit k is not set in arr[i] and is set in arr[j]
else if (((arr[i] & (1 << k)) == 0) &&
((arr[j] & (1 << k)) != 0)) {
count++;
}
}
}
}
return count;
}
static void Main() {
int[] arr = { 4, 14, 4, 14 };
int ans = totHammingDist(arr);
Console.WriteLine(ans);
}
}
function totHammingDist(arr) {
let count = 0;
let n = arr.length;
// Loop through all unique pairs (i, j)
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
// For each bit position from 0 to 30
for (let k = 0; k < 31; k++) {
// If bit k is set in arr[i] and not in arr[j]
if ((arr[i] & (1 << k)) && !(arr[j] & (1 << k))) {
count++;
}
// If bit k is not set in arr[i] and is set in arr[j]
else if(!(arr[i] & (1 << k)) && (arr[j] & (1 << k))) {
count++;
}
}
}
}
return count;
}
// Driver code
let arr = [4, 14, 4, 14];
let ans = totHammingDist(arr);
console.log(ans);
Output
8
[Expected Approach] - Bitwise Frequency Counting Using Array - O(n) Time and O(1) Space
Count the number of 1s at each bit position (0 to 31) across all numbers. For each bit, multiply the number of 1s with the number of 0s to get its contribution to the total Hamming distance.
- Initialize count as 0.
- Create a countone array of size 32 initialized to 0.
- Traverse each element of the array.
- For every number, iterate through bit positions 0 to 31.
- Check if the j-th bit is set. If set, increment countone[j].
- For each bit, compute contribution as countone[j] * (n - countone[j]) and add to count.
- Return count
#include <iostream>
#include <vector>
using namespace std;
int totHammingDist(vector<int> &arr){
int n = arr.size();
int count = 0;
vector<int> countone(32, 0);
// Count how many numbers have the j-th bit set
for (int i = 0; i < n; i++){
for (int j = 0; j < 32; j++){
// Check if j-th bit is set in arr[i]
if (arr[i] & (1 << j)){
countone[j]++;
}
}
}
// Compute contribution for each bit position
for (int j = 0; j < 32; j++){
count += countone[j] * (n - countone[j]);
}
return count;
}
int main(){
vector<int> arr = {4, 14, 4, 14};
int ans = totHammingDist(arr);
cout << ans << endl;
return 0;
}
import java.util.*;
class GfG {
static int totHammingDist(int[] arr) {
int n = arr.length;
int count = 0;
int[] countOne = new int[32];
// Count how many numbers have the j-th bit set
for (int num : arr) {
for (int j = 0; j < 32; j++) {
// Check if j-th bit is set in the current number
if ((num & (1 << j)) != 0) {
countOne[j]++;
}
}
}
// Compute contribution for each bit position
for (int j = 0; j < 32; j++) {
count += countOne[j] * (n - countOne[j]);
}
return count;
}
public static void main(String[] args) {
int[] arr = { 4, 14, 4, 14 };
int ans = totHammingDist(arr);
System.out.println(ans);
}
}
def totHammingDist(arr):
n = len(arr)
count = 0
count_one = [0] * 32
# Count how many numbers have the j-th bit set
for num in arr:
for j in range(32):
if num & (1 << j):
count_one[j] += 1
# Compute contribution for each bit position
for j in range(32):
count += count_one[j] * (n - count_one[j])
return count
if __name__ == "__main__":
arr = [4, 14, 4, 14]
ans = totHammingDist(arr)
print(ans)
using System;
class GfG {
static int totHammingDist(int[] arr){
int n = arr.Length;
int count = 0;
int[] countone = new int[32];
// Count how many numbers have the j-th bit set
for (int i = 0; i < n; i++) {
for (int j = 0; j < 32; j++) {
// Check if the j-th bit is set in arr[i]
if ((arr[i] & (1 << j)) != 0) {
countone[j]++;
}
}
}
// Compute contribution for each bit position
for (int j = 0; j < 32; j++) {
count += countone[j] * (n - countone[j]);
}
return count;
}
static void Main(){
int[] arr = { 4, 14, 4, 14 };
int ans = totHammingDist(arr);
Console.WriteLine(ans);
}
}
function totHammingDist(arr){
let n = arr.length;
let count = 0;
let countone = new Array(32).fill(0);
// Count how many numbers have the j-th bit set
for (let i = 0; i < n; i++) {
for (let j = 0; j < 32; j++) {
// Check if the j-th bit is set in arr[i]
if ((arr[i] & (1 << j)) !== 0) {
countone[j]++;
}
}
}
// Compute contribution for each bit position
for (let j = 0; j < 32; j++) {
count += countone[j] * (n - countone[j]);
}
return count;
}
// Driver Code
let arr = [4, 14, 4, 14];
console.log(totHammingDist(arr));
Output
8