Sum of Digit Differences of All Pairs - Solution & Explanation

Problem Overview: You receive an array of integers where every number has the same number of digits. For every pair of indices (i, j), compute how many digit positions differ between nums[i] and nums[j]. The goal is to return the total number of differing digit positions across all pairs.

Approach 1: Brute Force Pair Comparison (O(n² * d) time, O(1) space)

The most direct solution compares every pair of numbers. For each pair (i, j), iterate through their digits and count how many positions differ. If each number has d digits and there are n numbers, you perform roughly n(n-1)/2 comparisons, each scanning all digits. This approach uses simple iteration and basic digit extraction with division or string indexing. It works for small inputs and is useful for validating correctness, but it becomes too slow when n grows because pairwise comparison scales quadratically.

Approach 2: Digit Position Counting (O(n * d) time, O(d * 10) space)

The optimized idea processes digits position by position instead of pair by pair. For each digit index, maintain a frequency count of digits 0-9 seen so far. When you process a new number, check its digit at that position. Every previously seen number with a different digit contributes one difference for that position. If freq[x] stores how many times digit x has appeared at this position, then the number of new differing pairs is processed - freq[currentDigit]. Update the frequency and continue. This converts pair comparisons into counting operations using a small fixed-size array.

This technique relies on simple frequency counting, similar to problems in array processing and counting patterns. Instead of repeatedly comparing numbers, you aggregate digit statistics and compute contributions incrementally. Since digit values range only from 0 to 9, the memory footprint remains tiny.

The algorithm loops through all numbers and their digits exactly once, giving O(n * d) time. The auxiliary storage is a 2D structure storing digit frequencies per position, which costs O(d * 10) space. This is effectively constant for typical digit lengths.

Conceptually, the solution transforms a pairwise comparison problem into a frequency aggregation problem using ideas commonly seen with hash table-style counting.

Recommended for interviews: Interviewers expect the digit counting approach. Starting with the brute force method shows you understand the definition of the problem, but recognizing that digit positions are independent—and replacing pair comparisons with frequency counting—demonstrates stronger algorithmic thinking and reduces the complexity from quadratic to linear.