# Total Hamming Distance
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/total-hamming-distance)
Canonical: https://scaleengineer.com/dsa/problems/total-hamming-distance
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## Problem
The [Hamming distance](https://en.wikipedia.org/wiki/Hamming%5Fdistance) 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`.

**Example 1:**

**Input:** nums = [4,14,2]
**Output:** 6
**Explanation:** In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
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

**Constraints:**

* `1 <= nums.length <= 104`
* `0 <= nums[i] <= 109`
* The answer for the given input will fit in a **32-bit** integer.

# Approaches
## Brute Force: Pairwise Comparison
This approach directly follows the problem definition. It iterates through every possible pair of numbers in the input array, calculates the Hamming distance for each pair, and sums them up to get the total.
**Time:** O(N^2). We have two nested loops to iterate through all N * (N-1) / 2 pairs. For each pair, calculating the Hamming distance takes constant time (as integers have a fixed number of bits, e.g., 32). Thus, the overall complexity is quadratic. · **Space:** O(1). The algorithm uses a fixed amount of extra space for variables like `totalDistance` and loop counters, regardless of the input size.
**Pros:** It is simple to understand and implement.; The logic directly maps to the problem's definition.; It uses constant extra space.
**Cons:** The time complexity is O(N^2), which is too slow for the given constraints (N up to 10^4).; This approach will likely result in a 'Time Limit Exceeded' (TLE) error on most online judges.
### Explanation
The brute-force method is the most straightforward way to solve the problem. It involves generating all possible unique pairs of numbers from the input array and calculating the Hamming distance for each one.

To do this, we can use a nested loop. The outer loop runs from `i = 0` to `n-1` and the inner loop from `j = i + 1` to `n-1`, where `n` is the length of the array. This ensures that we consider each pair exactly once.

For each pair `(nums[i], nums[j])`, we calculate their Hamming distance. A clever way to do this is to use the bitwise XOR operator (`^`). The result of `nums[i] ^ nums[j]` is an integer where a bit is set to 1 if and only if the corresponding bits in `nums[i]` and `nums[j]` were different. Therefore, the number of set bits in the XOR result is equal to the Hamming distance. Most languages provide a built-in function to count set bits (e.g., `Integer.bitCount()` in Java), which simplifies this step.

We maintain a running sum, and for each pair, we add their calculated Hamming distance to this sum. After the loops complete, this sum is the total Hamming distance for all pairs.

```java
class Solution {
    public int totalHammingDistance(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return 0;
        }
        
        int totalDistance = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Calculate the XOR of the two numbers
                int xorResult = nums[i] ^ nums[j];
                // The number of set bits in the XOR result is the Hamming distance
                totalDistance += Integer.bitCount(xorResult);
            }
        }
        
        return totalDistance;
    }
}
```
### Algorithm
- Initialize a variable `totalDistance` to 0.
- Get the length of the array, `n`.
- Use a nested loop to iterate through all unique pairs of indices `(i, j)` where `0 <= i < j < n`.
- For each pair of numbers `(nums[i], nums[j])`:
  - Calculate their bitwise XOR: `xorResult = nums[i] ^ nums[j]`.
  - Count the number of set bits (1s) in `xorResult`. This can be done efficiently using a built-in function like `Integer.bitCount()`.
  - Add this count to `totalDistance`.
- After iterating through all pairs, return `totalDistance`.

## Optimized Approach: Bitwise Contribution
Instead of comparing pairs of numbers, this more efficient approach considers the problem from a bit-level perspective. It calculates the total Hamming distance by summing up the contributions of each individual bit position (from 0 to 31) across all numbers.
**Time:** O(N * K), where N is the number of elements in the array and K is the number of bits in the integer type (e.g., 32). Since K is a constant, the complexity is effectively linear, O(N). This is a significant improvement over the O(N^2) brute-force approach. · **Space:** O(1). We only use a few variables for the total sum, counts, and loop indices, which does not depend on the size of the input array.
**Pros:** Highly efficient with a linear time complexity, O(N).; Easily passes the time limits for the given constraints.; Maintains a constant space complexity.
**Cons:** The logic is less direct than the brute-force approach and requires thinking about the problem from a bit-level perspective.
### Explanation
A more optimal approach is to change the perspective. Instead of summing the distances pair by pair, we can sum the contributions of each bit position to the total distance. The total Hamming distance is the sum of distances at each bit position.

For any single bit position (say, the `i`-th bit), its contribution to the total Hamming distance is the number of pairs of numbers in the array that have different values at this bit. If we can calculate this for each bit and sum them up, we get the final answer.

Let's focus on one bit position, `i`. We can iterate through all the numbers in `nums` and count how many of them have a '1' at this position. Let this count be `k`. Since there are `n` numbers in total, it means `n - k` numbers must have a '0' at this position.

To form a pair with different bits at position `i`, we must choose one number from the group of `k` numbers (with a '1') and one number from the group of `n - k` numbers (with a '0'). The total number of such pairs is `k * (n - k)`. Each of these pairs contributes exactly 1 to the total Hamming distance at this specific bit position.

By repeating this process for all 31 relevant bit positions (for numbers up to 10^9) and summing up the results (`k * (n - k)` for each bit), we arrive at the total Hamming distance for all pairs.

```java
class Solution {
    public int totalHammingDistance(int[] nums) {
        int totalDistance = 0;
        int n = nums.length;
        // Iterate through each bit position from 0 to 30
        // (since 10^9 < 2^30, we only need to check up to bit 30).
        for (int i = 0; i < 31; i++) {
            int countOnes = 0;
            // For the current bit i, count how many numbers have it set
            for (int num : nums) {
                if (((num >> i) & 1) == 1) {
                    countOnes++;
                }
            }
            // The number of numbers with a 0 at bit i is n - countOnes
            int countZeros = n - countOnes;
            // The contribution from this bit is the number of pairs with different bits
            totalDistance += countOnes * countZeros;
        }
        return totalDistance;
    }
}
```
### Algorithm
- Initialize `totalDistance` to 0 and `n` to the length of the `nums` array.
- Iterate through each bit position `i` from 0 to 30 (since numbers are less than 2^31).
- For each bit position `i`:
  - Initialize a counter `countOnes` to 0.
  - Iterate through each number `num` in the `nums` array.
  - Check if the `i`-th bit of `num` is set. This can be done using the expression `((num >> i) & 1) == 1`.
  - If the bit is set, increment `countOnes`.
  - After counting, calculate the number of elements with a '0' at this bit position: `countZeros = n - countOnes`.
  - The contribution of this bit to the total distance is the number of pairs with different bits, which is `countOnes * countZeros`.
  - Add this product to `totalDistance`.
- After iterating through all bit positions, return `totalDistance`.

# Solutions
### Java

```java
class Solution {
public
  int totalHammingDistance(int[] nums) {
    int ans = 0;
    for (int i = 0; i < 31; ++i) {
      int a = 0, b = 0;
      for (int v : nums) {
        int t = (v >> i) & 1;
        a += t;
        b += t ^ 1;
      }
      ans += a * b;
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int: ans = 0 for i in range(31): a = b = 0 for v in nums: t = (v >> i) & 1 if t: a += 1 else: b += 1 ans += a * b return ans

```

### CPP

```cpp
class Solution {
public:
  int totalHammingDistance(vector<int> &nums) {
    int ans = 0;
    for (int i = 0; i < 31; ++i) {
      int a = 0, b = 0;
      for (int &v : nums) {
        int t = (v >> i) & 1;
        a += t;
        b += t ^ 1;
      }
      ans += a * b;
    }
    return ans;
  }
};

```