---
# System prepended metadata

title: LC 3153. Sum of Digit Differences of All Pairs
tags: [medium, leedcode, c++]

---

# 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<sup>5</sup></code>
- <code>1 <= nums[i] < 10<sup>9</sup></code>
- All integers in <code>nums</code> have the same number of digits.

## Solution 1
#### Python
#### C++
```cpp=
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