Skip to main content
Talentd

Sum of Digit Differences of All Pairs - Solution & Explanation

MediumArrayHash TableMathCounting17 min readAsked at: Google, Turing
Practice this problem

Problem Statement

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.

 

Example 1:

Input: nums = [13,23,12]

Output: 4

Explanation:
We have the following:
- The digit difference between 13 and 23 is 1.
- The digit difference between 13 and 12 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:

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

Approach Overview

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(n2 * 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.

Approach 1: Brute Force Approach

This approach involves comparing each pair of numbers in the array and counting the differences in corresponding digits.

This C program uses a function to calculate the digit difference between two numbers using string comparison. It loops over all pairs to compute the sum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2 * d), where n is the number of elements and d is the number of digits. Space Complexity: O(d) for storing string representations.

Try this approach in the editor →

Approach 2: Optimized Counting Approach

This approach optimizes by counting the differences in the same digit position across all numbers simultaneously. For one digit position, count how many numbers have each possible digit (0-9), and use this to calculate differences without pairwise comparison.

This solution counts the frequency of digits in each position, then calculates the sum of differences without direct pairwise checking, reducing computational effort.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * d), where n is the number of elements and d is the number of digits. Space Complexity: O(d*k) for digit counts.

Try this approach in the editor →

Approach 3: Counting

First, we get the number of digits m in the array. Then for each digit, we count the occurrence of each number at this digit in the array nums, denoted as cnt. Therefore, the sum of the digit differences of all number pairs at this digit is:

$ sum_{v \in cnt} v times (n - v)

where n is the length of the array. We add up the digit differences of all digits and divide by 2 to get the answer.

The time complexity is O(n times m), and the space complexity is O(C), where n and m are the length of the array and the number of digits in the numbers, respectively; and C is a constant, in this problem C = 10$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n^2 * d), where n is the number of elements and d is the number of digits. Space Complexity: O(d) for storing string representations.

Optimized Counting Approach

Time Complexity: O(n * d), where n is the number of elements and d is the number of digits. Space Complexity: O(d*k) for digit counts.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair ComparisonO(n^2 * d)O(1)Good for understanding the problem or when n is very small
Digit Position CountingO(n * d)O(d * 10)Optimal solution for large arrays; replaces pair comparisons with digit frequency counting

Video Solution

3153. Sum of Digit Differences of All Pairs | Arrays | Sum • Aryan Mittal • 4,767 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sum of Digit Differences of All Pairs easy or hard?
This problem is typically classified as Medium. The brute force idea is straightforward, but the key insight is recognizing that digit positions can be processed independently using counting. Identifying this optimization is what elevates the problem beyond an easy level.
How to solve Sum of Digit Differences of All Pairs in O(n)?
Treat each digit position independently. Maintain a frequency array for digits 0–9 at each position. While iterating through the numbers, count how many previously processed numbers have a different digit at that position using processed - freq[digit]. Summing these contributions across all digits produces the total in O(n * d) time.
What is the best approach for Sum of Digit Differences of All Pairs?
The most efficient solution counts digits at each position instead of comparing every pair of numbers. For each digit index, maintain a frequency array for digits 0–9 and compute how many previously seen digits differ from the current one. This reduces the complexity from O(n^2 * d) to O(n * d) while using only O(d * 10) extra space.
Is Sum of Digit Differences of All Pairs asked at Google/Amazon/Meta?
Digit counting and pair contribution problems appear frequently in interviews at companies like Amazon, Google, and Meta. The pattern of replacing pairwise comparisons with frequency aggregation is a common optimization technique tested in medium-level array and counting problems.
What data structure is used in Sum of Digit Differences of All Pairs?
The optimized solution primarily uses arrays for digit frequency counting. For each digit position, a small array of size 10 tracks how many times digits 0–9 appear. This lightweight counting structure plays a similar role to a hash table but with constant-size storage.
What is the time complexity of Sum of Digit Differences of All Pairs?
The optimal approach runs in O(n * d) time, where n is the number of integers and d is the number of digits in each number. Each number is processed once and each digit position performs constant-time frequency updates. The brute force approach takes O(n^2 * d) time because it compares every pair of numbers.
Sum of Digit Differences of All Pairs Python or Java solution approach?
Both Python and Java implementations follow the same strategy: iterate through numbers, extract digits by position, update frequency arrays, and accumulate pair contributions. The algorithm runs in O(n * d) time and uses O(d * 10) extra space regardless of the programming language.

Ready to solve this problem?

Practice Sum of Digit Differences of All Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Total Hamming Distance