Sum of Digit Differences of All Pairs — Medium Problem & Solution

Every integer in nums has the same number of digits. The digit difference of two integers is the count of positions at which their digits differ.

Difficulty: Medium
Topics: Arrays, Math, Hash Table, Counting
Asked at: Amazon, Google, Infosys
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Every integer in nums has the same number of digits. The digit difference of two integers is the count of positions at which their digits differ.

Return the sum of the digit differences over all pairs of integers in nums.

Example 1

Input: nums = [13,23,12]
Output: 4
Explanation: `13`/`23` differ in 1 place, `13`/`12` in 1, `23`/`12` in 2.

Example 2

Input: nums = [10,10,10,10]
Output: 0
Explanation: Identical numbers differ nowhere.

Example 3

Input: nums = [797,420,797]
Output: 6
Explanation: The two `797`s cost nothing; each against `420` costs 3.

Constraints

2 <= nums.length <= 1000
1 <= nums[i] < 10^9
All integers in nums have the same number of digits.

How to solve Sum of Digit Differences of All Pairs

Handle each digit position separately. At one position, count how many numbers carry each of the ten digits; the pairs that differ there are all pairs minus the pairs that agree, and the agreeing pairs are C(c, 2) summed over each digit's count c.

Approach

Find the shared digit count from the first number.
For each position, peel the last digit of every number with % 10 and tally the ten digits, then divide each number by 10.
Add C(n, 2) - Σ C(count[d], 2) to the running total.

Why it works

Counting the agreeing pairs instead of the differing ones is what avoids the O(n²) pairwise comparison: the tally is a single pass per position, and there are at most ten digits to combine. Peeling from the least significant end reuses the same array, so no string conversion is needed at all.

Complexity

Time — O(n · d) where d is the number of digits
Space — O(1) beyond a copy of the input

Pitfalls

Comparing every pair directly is O(n² · d) and far slower.
C(c, 2) is c * (c - 1) / 2; using c² counts ordered pairs and self-pairs.
Peel digits from a copy — the input should not be destroyed if the caller still needs it.

Reference solution

Python

from typing import List

def sumDigitDifferences(nums: List[int]) -> int:
    n = len(nums)
    work = nums[:]
    digits = len(str(nums[0]))
    total = 0
    for _ in range(digits):
        cnt = [0] * 10
        for i in range(n):
            cnt[work[i] % 10] += 1
            work[i] //= 10
        same = sum(c * (c - 1) // 2 for c in cnt)
        total += n * (n - 1) // 2 - same
    return total

JavaScript

var sumDigitDifferences = function(nums) {
    var n = nums.length, i, d;
    var work = nums.slice();
    var digits = 0;
    for (var v = nums[0]; v > 0; v = Math.floor(v / 10)) digits++;
    if (digits === 0) digits = 1;
    var total = 0;
    for (var p = 0; p < digits; p++) {
        var cnt = [];
        for (d = 0; d < 10; d++) cnt.push(0);
        for (i = 0; i < n; i++) {
            cnt[work[i] % 10]++;
            work[i] = Math.floor(work[i] / 10);
        }
        var same = 0;
        for (d = 0; d < 10; d++) same += cnt[d] * (cnt[d] - 1) / 2;
        total += n * (n - 1) / 2 - same;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue