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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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

1
2
3
4
5
6
7
8


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 <= 10^5
  • 1 <= nums[i] < 109
  • All integers in nums have the same number of digits.

Solution

Method 1 – Count by Digit Position

Intuition

For each digit position, count how many numbers have each digit (0-9). For every pair of numbers, if their digits at a position differ, it contributes 1 to the answer. For each position, the number of differing pairs is the number of pairs with different digits, which can be computed efficiently using counts.

Approach

  1. Convert all numbers to strings of equal length (since all have the same number of digits).
  2. For each digit position:
    • Count the frequency of each digit (0-9) at that position.
    • For each digit, the number of pairs with a different digit at this position is count[d] * (n - count[d]).
    • Sum for all digits, then divide by 2 (since each pair is counted twice).
  3. Sum over all positions.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    long long sumDigitDifferences(vector<int>& nums) {
        int n = nums.size();
        vector<string> s(n);
        int m = 0;
        for (int i = 0; i < n; ++i) {
            s[i] = to_string(nums[i]);
            m = max(m, (int)s[i].size());
        }
        for (int i = 0; i < n; ++i) {
            while (s[i].size() < m) s[i] = '0' + s[i];
        }
        long long ans = 0;
        for (int pos = 0; pos < m; ++pos) {
            vector<int> cnt(10);
            for (int i = 0; i < n; ++i) cnt[s[i][pos] - '0']++;
            for (int d = 0; d < 10; ++d) {
                ans += 1LL * cnt[d] * (n - cnt[d]);
            }
        }
        return ans / 2;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func sumDigitDifferences(nums []int) int64 {
    n := len(nums)
    s := make([]string, n)
    m := 0
    for i, v := range nums {
        s[i] = fmt.Sprintf("%d", v)
        if len(s[i]) > m {
            m = len(s[i])
        }
    }
    for i := 0; i < n; i++ {
        for len(s[i]) < m {
            s[i] = "0" + s[i]
        }
    }
    var ans int64
    for pos := 0; pos < m; pos++ {
        cnt := make([]int, 10)
        for i := 0; i < n; i++ {
            cnt[s[i][pos]-'0']++
        }
        for d := 0; d < 10; d++ {
            ans += int64(cnt[d]) * int64(n-cnt[d])
        }
    }
    return ans / 2
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public long sumDigitDifferences(int[] nums) {
        int n = nums.length;
        String[] s = new String[n];
        int m = 0;
        for (int i = 0; i < n; i++) {
            s[i] = String.valueOf(nums[i]);
            m = Math.max(m, s[i].length());
        }
        for (int i = 0; i < n; i++) {
            while (s[i].length() < m) s[i] = "0" + s[i];
        }
        long ans = 0;
        for (int pos = 0; pos < m; pos++) {
            int[] cnt = new int[10];
            for (int i = 0; i < n; i++) cnt[s[i].charAt(pos) - '0']++;
            for (int d = 0; d < 10; d++) ans += 1L * cnt[d] * (n - cnt[d]);
        }
        return ans / 2;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun sumDigitDifferences(nums: IntArray): Long {
        val n = nums.size
        val s = nums.map { it.toString() }.toMutableList()
        var m = s.maxOf { it.length }
        for (i in 0 until n) {
            while (s[i].length < m) s[i] = "0" + s[i]
        }
        var ans = 0L
        for (pos in 0 until m) {
            val cnt = IntArray(10)
            for (i in 0 until n) cnt[s[i][pos] - '0']++
            for (d in 0..9) ans += cnt[d].toLong() * (n - cnt[d])
        }
        return ans / 2
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def sumDigitDifferences(self, nums: list[int]) -> int:
        n = len(nums)
        s = [str(x) for x in nums]
        m = max(len(x) for x in s)
        s = [x.zfill(m) for x in s]
        ans = 0
        for pos in range(m):
            cnt = [0] * 10
            for i in range(n):
                cnt[int(s[i][pos])] += 1
            for d in range(10):
                ans += cnt[d] * (n - cnt[d])
        return ans // 2
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn sum_digit_differences(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut s: Vec<String> = nums.iter().map(|x| x.to_string()).collect();
        let m = s.iter().map(|x| x.len()).max().unwrap();
        for x in &mut s {
            while x.len() < m {
                *x = format!("0{}", x);
            }
        }
        let mut ans = 0i64;
        for pos in 0..m {
            let mut cnt = [0; 10];
            for i in 0..n {
                cnt[s[i].as_bytes()[pos] as usize - b'0' as usize] += 1;
            }
            for d in 0..10 {
                ans += cnt[d] as i64 * (n as i64 - cnt[d] as i64);
            }
        }
        ans / 2
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    sumDigitDifferences(nums: number[]): number {
        const n = nums.length;
        let s = nums.map(x => x.toString());
        const m = Math.max(...s.map(x => x.length));
        s = s.map(x => x.padStart(m, '0'));
        let ans = 0;
        for (let pos = 0; pos < m; pos++) {
            const cnt = new Array(10).fill(0);
            for (let i = 0; i < n; i++) cnt[+s[i][pos]]++;
            for (let d = 0; d < 10; d++) ans += cnt[d] * (n - cnt[d]);
        }
        return Math.floor(ans / 2);
    }
}

Complexity

  • ⏰ Time complexity: O(n * m) — Where n is the number of numbers and m is the number of digits. Each digit position is processed for all numbers.
  • 🧺 Space complexity: O(n * m) — For storing the string representations of numbers.