# Sum of Digit Differences of All Pairs
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-of-digit-differences-of-all-pairs)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-digit-differences-of-all-pairs
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
**Companies:** [Turing](https://scaleengineer.com/companies/turing)
---
## Problem
You are given an array `nums` consisting of **positive** integers where all integers have the **same** number of digits.

The **digit difference** between two integers is the _count_ of different digits that are in the **same** position in the two integers.

Return the **sum** of the **digit differences** between **all** pairs of integers in `nums`.

**Example 1:**

**Input:** nums = \[13,23,12\]

**Output:** 4

**Explanation:**  
We have the following:  
\- The digit difference between **1**3 and **2**3 is 1.  
\- The digit difference between 1**3** and 1**2** is 1.  
\- The digit difference between **23** and **12** is 2.  
So the total sum of digit differences between all pairs of integers is `1 + 1 + 2 = 4`.

**Example 2:**

**Input:** nums = \[10,10,10,10\]

**Output:** 0

**Explanation:**  
All the integers in the array are the same. So the total sum of digit differences between all pairs of integers will be 0.

**Constraints:**

* `2 <= nums.length <= 105`
* `1 <= nums[i] < 109`
* All integers in `nums` have the same number of digits.

# Approaches
## Brute Force Iteration
This approach directly translates the problem statement into code. It iterates through every unique pair of numbers in the input array, calculates the digit difference for each pair by comparing their digits one by one, and sums up these differences.
**Time:** O(N² * D), where N is the number of elements in `nums` and D is the number of digits in each number. There are O(N²) pairs, and for each pair, we perform O(D) work to compare all their digits. Given N can be up to 10⁵, this approach is too slow. · **Space:** O(1) extra space. We only use a few variables to store loop counters and the running sum.
**Pros:** Simple to understand and straightforward to implement.
**Cons:** Highly inefficient due to its quadratic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the problem constraints.
### Explanation
The algorithm employs two nested loops to generate all unique pairs of numbers, `(nums[i], nums[j])` where `i < j`. For each pair, an inner loop is used to compare their digits at each position. To extract digits, the numbers are repeatedly divided by 10, and the remainder (`% 10`) gives the last digit. This process continues from the least significant digit to the most significant. A global counter for the total difference is maintained and incremented for each position where the digits of the pair do not match. The final sum is returned after all pairs have been processed.

```java
class Solution {
    public long sumDigitDifferences(int[] nums) {
        long totalDifference = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int num1 = nums[i];
                int num2 = nums[j];
                
                // Since all numbers have the same number of digits,
                // we can iterate while one of them is > 0.
                while (num1 > 0) {
                    if (num1 % 10 != num2 % 10) {
                        totalDifference++;
                    }
                    num1 /= 10;
                    num2 /= 10;
                }
            }
        }
        return totalDifference;
    }
}
```
### Algorithm
- Initialize a variable `totalDifference` to 0.
- Use two nested loops to iterate through all unique pairs of indices `(i, j)` where `i < j`.
- For each pair `(nums[i], nums[j])`:
  - Create temporary copies of the numbers, say `num1` and `num2`.
  - Start a loop that continues as long as the numbers are positive (since all have the same length, checking one is sufficient).
  - In each iteration of this inner loop, extract the last digit of `num1` and `num2` using the modulo operator (`% 10`).
  - If the digits are different, increment `totalDifference`.
  - Update `num1` and `num2` by dividing them by 10 to process the next digit.
- After iterating through all pairs, return `totalDifference`.

## Digit-by-Digit Contribution
This optimized approach reframes the problem to achieve a much better time complexity. Instead of iterating through pairs of numbers, it iterates through each digit position (units, tens, hundreds, etc.) and calculates the total contribution to the sum from that position. The final answer is the sum of these contributions.
**Time:** O(N * D), where N is the number of elements in `nums` and D is the number of digits. We have an outer loop that runs D times, and an inner loop that runs N times. This is a significant improvement over the brute-force approach. · **Space:** O(1) extra space. We only need a constant-size array (`counts`) of size 10 for frequencies and a few variables for calculations, regardless of the input size.
**Pros:** Highly efficient with a linear time complexity relative to the total number of digits in the input.; Easily handles the maximum constraints of the problem.
**Cons:** The logic is less direct than the brute-force approach and requires a change in perspective to understand.
### Explanation
The core idea is that the total sum of digit differences is the sum of differences calculated independently at each digit position. The algorithm iterates from the least significant digit to the most significant. For each position, it first counts the frequency of each digit (0-9) across all numbers in the input array. This is done by iterating through `nums` and using modular arithmetic to isolate the digit at the current position.

Once the frequencies are known for a position, we can calculate how many pairs have different digits at this position. If `c` numbers have a digit `d`, and there are `n` numbers in total, then these `c` numbers can be paired with `n - c` numbers that have a different digit. This contributes `c * (n - c)` to a running sum. By summing this value over all possible digits (0-9), we get the total number of differing pairs, but with each pair counted twice. Therefore, the contribution for the current position is `(sum of c * (n - c)) / 2`.

This process is repeated for all digit positions, and their contributions are summed up to get the final result.

```java
class Solution {
    public long sumDigitDifferences(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }

        long totalDifference = 0;
        // All numbers have the same number of digits.
        int numDigits = String.valueOf(nums[0]).length();
        long divisor = 1;

        for (int p = 0; p < numDigits; p++) {
            int[] counts = new int[10];
            for (int num : nums) {
                int digit = (int) ((num / divisor) % 10);
                counts[digit]++;
            }

            long positionDifference = 0;
            for (int count : counts) {
                positionDifference += (long)count * (n - count);
            }
            totalDifference += positionDifference / 2;
            
            if (p < numDigits - 1) {
                divisor *= 10;
            }
        }

        return totalDifference;
    }
}
```
### Algorithm
- The total sum of differences can be seen as the sum of contributions from each digit position.
- Initialize `totalDifference = 0L`.
- Determine the number of digits, `D`, from any number in the array (e.g., `String.valueOf(nums[0]).length()`).
- Loop through each digit position `p` from 0 to `D-1` (from units place upwards).
  - For each position `p`:
    - Initialize a frequency array `counts = new int[10]` to store the counts of digits 0-9.
    - Iterate through each number `num` in the `nums` array.
    - Extract the digit at position `p` using `(num / divisor) % 10`, where `divisor` is 10ᵖ.
    - Increment the frequency of the extracted digit in the `counts` array.
    - After counting all digits for the current position, calculate the number of pairs with different digits.
    - For each digit `d` (0-9), if its count is `c`, it forms `c * (n - c)` pairs with numbers that have a different digit at this position.
    - Sum `c * (n - c)` for all `d`. This sum counts each differing pair twice, so divide it by 2 to get the contribution for the current position.
    - Add this contribution to `totalDifference`.
- After iterating through all digit positions, return `totalDifference`.

# Solutions
### Java

```java
class Solution {
public
  long sumDigitDifferences(int[] nums) {
    int n = nums.length;
    int m = (int)Math.floor(Math.log10(nums[0])) + 1;
    int[] cnt = new int[10];
    long ans = 0;
    for (int k = 0; k < m; ++k) {
      Arrays.fill(cnt, 0);
      for (int i = 0; i < n; ++i) {
        ++cnt[nums[i] % 10];
        nums[i] /= 10;
      }
      for (int i = 0; i < 10; ++i) {
        ans += 1L * cnt[i] * (n - cnt[i]);
      }
    }
    return ans / 2;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long sumDigitDifferences(vector<int> &nums) {
    int n = nums.size();
    int m = floor(log10(nums[0])) + 1;
    int cnt[10];
    long long ans = 0;
    for (int k = 0; k < m; ++k) {
      memset(cnt, 0, sizeof(cnt));
      for (int i = 0; i < n; ++i) {
        ++cnt[nums[i] % 10];
        nums[i] /= 10;
      }
      for (int i = 0; i < 10; ++i) {
        ans += 1LL * (cnt[i] * (n - cnt[i]));
      }
    }
    return ans / 2;
  }
};

```

### Python

```python
class Solution:
    def sumDigitDifferences(self, nums: List[int]) -> int: n = len(nums) m = int(log10(nums[0])) + 1 ans = 0 for _ in range(m): cnt = Counter() for i, x in enumerate(nums): nums[i], y = divmod(x, 10) cnt[y] += 1 ans += sum(v * (n - v) for v in cnt . values()) // 2 return ans

```