LeetCode 3153 - Sum of Digit Differences of All Pairs

LeetCode Problem 3153

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Counting

Solution

Problem Understanding

The problem asks us to compute the total digit difference across every pair of numbers in the array.

All numbers have the same number of digits. For any two numbers, their digit difference is defined as the number of positions where the digits are different.

For example:

• 13 and 23 differ only at the first digit, so their digit difference is 1
• 23 and 12 differ at both positions, so their digit difference is 2

We must compute this value for every possible pair and return the total sum.

The input is an array nums of positive integers. Every integer has the same digit length, which is important because it guarantees that digit positions align correctly across all numbers.

The constraints are large:

• Up to 10^5 numbers
• Each number can have up to 9 digits

A naive pairwise comparison would require checking every pair of numbers, which would result in approximately 10^10 operations in the worst case. That is far too slow.

The key observation is that digit positions are independent. Instead of comparing every pair of numbers directly, we can process one digit position at a time and count how many pairs differ at that position.

Important edge cases include:

• All numbers being identical, which should produce 0
• Only two numbers in the array
• Numbers with repeated digits
• Large inputs where performance matters
• Leading positions where many digits are equal

The problem guarantees that all numbers have the same number of digits, so we do not need to handle padding or unequal lengths.

Approaches

Brute Force Approach

The brute force solution compares every pair of numbers.

For each pair:

1. Convert both numbers into strings
2. Compare digits position by position
3. Count how many positions differ
4. Add that count to the final answer

This approach is correct because it directly follows the definition of digit difference.

However, there are O(n^2) pairs. With n = 10^5, this becomes infeasible.

If each number has d digits, then the total complexity becomes O(n^2 * d).

Optimal Approach

The important insight is that digit positions can be processed independently.

Suppose we focus on a single digit position.

At that position:

• Some numbers contain digit 0
• Some contain digit 1
• Some contain digit 2
• and so on

Instead of comparing every pair explicitly, we count how many pairs have different digits.

For a particular digit:

• If count[d] numbers contain digit d
• Then each of those numbers forms differing pairs with all previously seen numbers that had a different digit

A cleaner way to think about it is:

For each position:

• Total pairs at this position = all pairs of numbers
• Pairs with equal digits do not contribute
• Pairs with different digits contribute 1

We can process the array incrementally.

As we iterate through numbers:

• Maintain frequency counts for each digit at each position

• When processing a new digit:

• Previous numbers seen so far = i

• Numbers with same digit = freq[digit]

• Numbers with different digit = i - freq[digit]

• Add that value to the answer

This avoids pairwise comparisons entirely.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² × d)	O(1)	Compare every pair digit by digit
Optimal	O(n × d)	O(d × 10)	Count differing digits position-wise

Here, d is the number of digits per number.

Algorithm Walkthrough

1. Determine the number of digit positions.

Since all numbers have the same number of digits, we can convert the first number to a string and use its length. 2. Create a frequency table for every digit position.

For each position, we need counts of digits 0 through 9.

A 2D array works well:

• digit_counts[position][digit]

3. Initialize the answer to 0.
4. Iterate through the numbers one by one.

While processing the i-th number, all previous numbers have already been counted in the frequency table. 5. Convert the current number into a string.

This makes digit access straightforward. 6. For each digit position:

• Extract the current digit
• Find how many previous numbers had the same digit at this position
• Previous numbers count = i
• Different digits count = i - same_digit_count
• Add this value to the answer

7. Update the frequency table.

After processing contributions, increment the frequency count for the current digit. 8. Return the final answer.

Why it works

For every digit position, each pair contributes exactly once if the digits differ.

When processing the current number, we count how many previously processed numbers have a different digit at the same position. This guarantees:

• Every valid pair is counted exactly once
• No pair is missed
• No pair is double counted

Because positions are independent, summing contributions across all positions gives the total digit difference across all pairs.

Python Solution

from typing import List

class Solution:
    def sumDigitDifferences(self, nums: List[int]) -> int:
        digit_length = len(str(nums[0]))
        
        # digit_counts[position][digit]
        digit_counts = [[0] * 10 for _ in range(digit_length)]
        
        total_difference = 0
        
        for index, number in enumerate(nums):
            digits = str(number)
            
            for position, ch in enumerate(digits):
                digit = int(ch)
                
                same_digit_count = digit_counts[position][digit]
                different_digit_count = index - same_digit_count
                
                total_difference += different_digit_count
                
                digit_counts[position][digit] += 1
        
        return total_difference

The implementation starts by determining the number of digit positions using the first number.

A two-dimensional frequency table is then created. Each row corresponds to a digit position, and each column corresponds to a digit from 0 to 9.

As we iterate through the numbers:

• index tells us how many previous numbers exist

• For each digit position:

• We look up how many previous numbers had the same digit

• Subtracting from index gives how many previous numbers differ

• That value contributes directly to the answer

After calculating the contribution, we update the frequency table so future numbers can use this information.

The algorithm processes each digit exactly once, making it highly efficient.

Go Solution

func sumDigitDifferences(nums []int) int64 {
	digitLength := len([]byte(string(rune(nums[0]))))

	// Better approach for digit length
	temp := nums[0]
	digitLength = 0
	for temp > 0 {
		digitLength++
		temp /= 10
	}

	digitCounts := make([][10]int, digitLength)

	var totalDifference int64 = 0

	for index, number := range nums {
		digits := make([]int, digitLength)

		tempNum := number

		for pos := digitLength - 1; pos >= 0; pos-- {
			digits[pos] = tempNum % 10
			tempNum /= 10
		}

		for position, digit := range digits {
			sameDigitCount := digitCounts[position][digit]
			differentDigitCount := index - sameDigitCount

			totalDifference += int64(differentDigitCount)

			digitCounts[position][digit]++
		}
	}

	return totalDifference
}

The Go implementation avoids repeated string conversions for performance reasons.

Instead, digits are extracted mathematically using modulo and division operations.

One important difference is the return type. The function returns int64 because the total number of differing pairs can exceed the range of a standard 32-bit integer.

The frequency table uses a slice of fixed-size arrays:

[][10]int

This is memory efficient and provides fast indexing.

Worked Examples

Example 1

Input:

nums = [13, 23, 12]

Initial state:

Position	Digit Counts
0	all zeros
1	all zeros

Process 13

Digits:

• Position 0 → 1
• Position 1 → 3

Position	Digit	Previous Different	Total
0	1	0	0
1	3	0	0

Update counts.

Process 23

Digits:

• Position 0 → 2
• Position 1 → 3

Position	Digit	Previous Different	Total
0	2	1	1
1	3	0	1

At position 0, digit 2 differs from previous digit 1.

Update counts.

Process 12

Digits:

• Position 0 → 1
• Position 1 → 2

Position	Digit	Previous Different	Total
0	1	1	2
1	2	2	4

Final answer:

4

Example 2

Input:

nums = [10, 10, 10, 10]

Every digit at every position matches.

Each step adds 0 differing pairs.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × d)	Each digit of each number is processed once
Space	O(d × 10)	Frequency table for each position and digit

The algorithm scales linearly with the number of integers and the number of digits.

Since the maximum digit count is at most 9, the practical runtime is extremely efficient.

The space usage is also very small because we only store counts for digits 0 through 9 at each position.

Test Cases

from typing import List

class Solution:
    def sumDigitDifferences(self, nums: List[int]) -> int:
        digit_length = len(str(nums[0]))
        digit_counts = [[0] * 10 for _ in range(digit_length)]
        
        total_difference = 0
        
        for index, number in enumerate(nums):
            digits = str(number)
            
            for position, ch in enumerate(digits):
                digit = int(ch)
                
                same_digit_count = digit_counts[position][digit]
                total_difference += index - same_digit_count
                
                digit_counts[position][digit] += 1
        
        return total_difference

solution = Solution()

assert solution.sumDigitDifferences([13, 23, 12]) == 4  # Provided example
assert solution.sumDigitDifferences([10, 10, 10, 10]) == 0  # All identical
assert solution.sumDigitDifferences([11, 12]) == 1  # Single differing digit
assert solution.sumDigitDifferences([12, 34]) == 2  # Both digits differ
assert solution.sumDigitDifferences([111, 111, 111]) == 0  # Repeated identical numbers
assert solution.sumDigitDifferences([123, 321]) == 2  # Partial differences
assert solution.sumDigitDifferences([90, 91, 92]) == 2  # Only last digit changes
assert solution.sumDigitDifferences([100, 200, 300]) == 3  # First digit differs
assert solution.sumDigitDifferences([999999999, 111111111]) == 9  # Maximum digit length
assert solution.sumDigitDifferences([55, 56, 57, 58]) == 6  # Multiple differing pairs

Test	Why
[13, 23, 12]	Verifies provided example
[10, 10, 10, 10]	Ensures identical numbers produce zero
[11, 12]	Smallest meaningful differing case
[12, 34]	Every digit differs
[111, 111, 111]	Repeated identical values
[123, 321]	Mixed matching and differing positions
[90, 91, 92]	Single position changes repeatedly
[100, 200, 300]	Leading digit differences
[999999999, 111111111]	Maximum digit length
[55, 56, 57, 58]	Multiple combinations of differing digits

Edge Cases

One important edge case is when all numbers are identical. In this situation, every digit at every position matches across all pairs. A buggy implementation might accidentally overcount pairs or fail to recognize that no differences exist. This implementation handles it naturally because index - same_digit_count becomes zero at every step.

Another important case is when there are only two numbers in the array. Since there is only one pair, the algorithm must correctly compute the exact digit difference between them. The counting approach still works because the second number compares itself against the single previously processed number.

A third edge case involves very large inputs. With 10^5 numbers, any quadratic approach will time out. The optimized solution avoids explicit pair comparisons entirely and processes each digit once, ensuring the runtime remains efficient even at maximum constraints.

A fourth subtle edge case is repeated digits at some positions but not others. For example, numbers like [101, 111, 121] share digits at multiple positions while differing at others. The implementation handles this correctly because each digit position is processed independently using separate frequency counts.