# LC 3153. Sum of Digit Differences of All Pairs

### [Problem link](https://leetcode.com/problems/sum-of-digit-differences-of-all-pairs/)

###### tags: `leedcode` `medium` `c++`

You are given an array <code>nums</code> 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 <code>nums</code>.

**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 <code>1 + 1 + 2 = 4</code>.

**Example 2:**

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

Output: 0

Explanation:<br />
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:**

- <code>2 <= nums.length <= 10⁵</code>
- <code>1 <= nums[i] < 10⁹</code>
- All integers in <code>nums</code> have the same number of digits.

## Solution 1
#### Python
#### C++

class Solution {
public:
    long long sumDigitDifferences(vector<int>& nums) {
        vector<vector<int>> freq(10, vector<int>(10, 0));
        for (int num: nums) {
            int level = 0;
            while (num > 0) {
                freq[level][num % 10]++;
                level++;
                num /= 10;
            }
        }

        long long res = 0;
        for (int i = 0; i < freq.size(); i++) {
            for (int j = 0; j < freq[0].size(); j++) {
                res += freq[i][j] * (nums.size() - freq[i][j]);
            }
        }
        return res / 2;
    }
};

>### Complexity
>n = nums.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(100) |

## Note
sol1:
[0, 5, 6, 6, 6, 8, 8]
0: res += 1 * 6(5, 6, 6, 6, 8, 8)
5: res += 1 * 6(0, 6, 6, 6, 8, 8)
6: res += 3 * 4(0, 5, 8, 8)
6: res += 3 * 4(0, 5, 8, 8)
6: res += 3 * 4(0, 5, 8, 8)
8: res += 2 * 4(0, 5, 6, 6, 6)
8: res += 2 * 4(0, 5, 6, 6, 6)
res /= 2