Sum of Digit Differences of All Pairs solution and explanation
Google
9 more videos on this problem
3153. Sum of Digit Differences of All Pairs | Arrays | SumAryan Mittal · 15:41 · 4K views
3153. Sum of Digit Differences of All Pairs (Leetcode Medium)Programming Live with Larry · 7:19 · 494 views
Leetcode 3153 | Sum of Digit Differences of All Pairs | Weekly Contest 398Road To FAANG · 6:58 · 280 views
3153. Sum of Digit Differences of All Pairs - Leetcode Medium - DSA - Hashmap.THE CODE CLUB · 12:02 · 180 views
3153. Sum of Digit Differences of All Pairs | Map | Logic | Math | Array | C++ | Leetcode | MediumLeet's Code · 12:06 · 167 views
3153 Sum of Digit Differences of All Pairs || Leetcode solutionMukto Academy Global · 5:44 · 130 views
LeetCode Weekly Contest 398 || 3152. Special Array II || 3153. Sum of Digit Differences of All PairsHighlights Point Coding · 17:09 · 103 views
#LC.3153.# Sum of Digit Diff. of All Pairs#DECODE DSA # LEVEL UP#MISCELLANEOUS #leetcode#challengeDecode · 10:42 · 53 views
Sum Of Digit Differences Of All Pairs #leetcode #contest #coding #codingtutorial #leetcodesolutionBKC Coders · 10:10 · 30 views
［力扣每日一題］ LC 3153. 所有数对中数位差之和 - 1645 Medium - Java - HashArray 哈希數組、digit decomposition拆位法Leetcode刷題最後希望 · 8:57 · 5 views
The 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.
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 <= 1051 <= nums[i] < 109- All integers in
numshave 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.
def digit_difference(a, b):
return sum(1 for x, y in zip(str(a), str(b)) if x != y)
def sum_of_digit_differences(nums):
total = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
total += digit_difference(nums[i], nums[j])
return total
nums = [13, 23, 12]
print(sum_of_digit_differences(nums))public class Main {
public static int digitDifference(int a, int b) {
int diff = 0;
String aStr = Integer.toString(a);
String bStr = Integer.toString(b);
for (int i = 0; i < aStr.length(); i++) {
if (aStr.charAt(i) != bStr.charAt(i)) {
diff++;
}
}
return diff;
}
public static int sumOfDigitDifferences(int[] nums) {
int sum = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
sum += digitDifference(nums[i], nums[j]);
}
}
return sum;
}
public static void main(String[] args) {
int[] nums = { 13, 23, 12 };
System.out.println(sumOfDigitDifferences(nums));
}
}#include <iostream>
#include <string>
int digitDifference(int a, int b) {
int diff = 0;
std::string a_str = std::to_string(a);
std::string b_str = std::to_string(b);
for (int i = 0; i < a_str.length(); i++) {
if (a_str[i] != b_str[i]) {
diff++;
}
}
return diff;
}
int sumOfDigitDifferences(int nums[], int size) {
int sum = 0;
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
sum += digitDifference(nums[i], nums[j]);
}
}
return sum;
}
int main() {
int nums[] = {13, 23, 12};
int size = sizeof(nums) / sizeof(nums[0]);
std::cout << sumOfDigitDifferences(nums, size);
return 0;
}function digitDifference(a, b) {
let diff = 0;
let aStr = a.toString();
let bStr = b.toString();
for (let i = 0; i < aStr.length; i++) {
if (aStr[i] !== bStr[i]) {
diff++;
}
}
return diff;
}
function sumOfDigitDifferences(nums) {
let sum = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
sum += digitDifference(nums[i], nums[j]);
}
}
return sum;
}
let nums = [13, 23, 12];
console.log(sumOfDigitDifferences(nums));#include <stdio.h>
#include <string.h>
int digitDifference(int a, int b) {
int diff = 0;
char a_str[12], b_str[12];
sprintf(a_str, "%d", a);
sprintf(b_str, "%d", b);
for (int i = 0; i < strlen(a_str); i++) {
if (a_str[i] != b_str[i]) {
diff++;
}
}
return diff;
}
int sumOfDigitDifferences(int nums[], int size) {
int sum = 0;
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
sum += digitDifference(nums[i], nums[j]);
}
}
return sum;
}
int main() {
int nums[] = {13, 23, 12};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d", sumOfDigitDifferences(nums, size));
return 0;
}using System;
class Program {
public static int DigitDifference(int a, int b) {
int diff = 0;
string aStr = a.ToString();
string bStr = b.ToString();
for (int i = 0; i < aStr.Length; i++) {
if (aStr[i] != bStr[i]) {
diff++;
}
}
return diff;
}
public static int SumOfDigitDifferences(int[] nums) {
int sum = 0;
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
sum += DigitDifference(nums[i], nums[j]);
}
}
return sum;
}
static void Main() {
int[] nums = { 13, 23, 12 };
Console.WriteLine(SumOfDigitDifferences(nums));
}
}This Python solution utilizes generator expressions to compute digit differences in all number pairs via zipping their string representations.
Time Complexity: O(n^2 * d), where n is the number of elements and d is the total number of digits. Space Complexity: O(1) since strings are handled internally.
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.
def sum_of_digit_differences(nums):
num_digits = len(str(nums[0]))
digit_count = [[0] * 10 for _ in range(num_digits)]
for num in nums:
for i in range(num_digits - 1, -1, -1):
digit_count[i][num % 10] += 1
num //= 10
total_sum = 0
for d in range(num_digits):
column_sum = sum(k * digit_count[d][k] for k in range(10))
for k in range(10):
total_sum += digit_count[d][k] * (column_sum - digit_count[d][k] * k)
return total_sum // 2
nums = [13, 23, 12]
print(sum_of_digit_differences(nums))import java.util.*;
public class Main {
public static int sumOfDigitDifferences(int[] nums) {
int numDigits = String.valueOf(nums[0]).length();
int[][] digitCount = new int[numDigits][10];
for (int num : nums) {
for (int i = numDigits - 1; i >= 0; i--) {
digitCount[i][num % 10]++;
num /= 10;
}
}
int sum = 0;
for (int d = 0; d < numDigits; d++) {
int columnSum = 0;
for (int k = 0; k < 10; k++) {
columnSum += k * digitCount[d][k];
}
for (int k = 0; k < 10; k++) {
sum += digitCount[d][k] * (columnSum - digitCount[d][k] * k);
}
}
return sum / 2;
}
public static void main(String[] args) {
int[] nums = {13, 23, 12};
System.out.println(sumOfDigitDifferences(nums));
}
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int sumOfDigitDifferences(vector<int>& nums) {
int num_digits = log10(nums[0]) + 1;
vector<vector<int>> digit_count(num_digits, vector<int>(10, 0));
for (int num : nums) {
for (int i = num_digits - 1; i >= 0; i--) {
digit_count[i][num % 10]++;
num /= 10;
}
}
int sum = 0;
for (int d = 0; d < num_digits; d++) {
int column_sum = 0;
for (int k = 0; k < 10; k++) {
column_sum += k * digit_count[d][k];
}
for (int k = 0; k < 10; k++) {
sum += digit_count[d][k] * (column_sum - digit_count[d][k] * k);
}
}
sum /= 2;
return sum;
}
int main() {
vector<int> nums = {13, 23, 12};
cout << sumOfDigitDifferences(nums) << endl;
return 0;
}function sumOfDigitDifferences(nums) {
const numDigits = nums[0].toString().length;
const digitCount = Array.from({ length: numDigits }, () => Array(10).fill(0));
for (let num of nums) {
for (let i = numDigits - 1; i >= 0; i--) {
digitCount[i][num % 10]++;
num = Math.floor(num / 10);
}
}
let sum = 0;
for (let d = 0; d < numDigits; d++) {
let columnSum = 0;
for (let k = 0; k < 10; k++) {
columnSum += k * digitCount[d][k];
}
for (let k = 0; k < 10; k++) {
sum += digitCount[d][k] * (columnSum - digitCount[d][k] * k);
}
}
return sum / 2;
}
const nums = [13, 23, 12];
console.log(sumOfDigitDifferences(nums));#include <stdio.h>
#include <string.h>
int sumOfDigitDifferences(int nums[], int size) {
int num_digits = snprintf(NULL, 0, "%d", nums[0]);
int digit_count[num_digits][10];
memset(digit_count, 0, sizeof(digit_count));
for (int i = 0; i < size; i++) {
int n = nums[i];
for (int j = num_digits - 1; j >= 0; j--) {
digit_count[j][n % 10]++;
n /= 10;
}
}
int sum = 0;
for (int d = 0; d < num_digits; d++) {
int column_sum = 0;
for (int k = 0; k < 10; k++) {
column_sum += digit_count[d][k] * k;
}
for (int k = 0; k < 10; k++) {
sum += digit_count[d][k] * (column_sum - digit_count[d][k] * k);
}
}
sum /= 2;
return sum;
}
int main() {
int nums[] = {13, 23, 12};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d", sumOfDigitDifferences(nums, size));
return 0;
}using System;
class Program {
public static int SumOfDigitDifferences(int[] nums) {
int numDigits = nums[0].ToString().Length;
int[,] digitCount = new int[numDigits, 10];
foreach (int num in nums) {
int n = num;
for (int i = numDigits - 1; i >= 0; i--) {
digitCount[i, n % 10]++;
n /= 10;
}
}
int sum = 0;
for (int d = 0; d < numDigits; d++) {
int columnSum = 0;
for (int k = 0; k < 10; k++) {
columnSum += k * digitCount[d, k];
}
for (int k = 0; k < 10; k++) {
sum += digitCount[d, k] * (columnSum - digitCount[d, k] * k);
}
}
return sum / 2;
}
static void Main() {
int[] nums = { 13, 23, 12 };
Console.WriteLine(SumOfDigitDifferences(nums));
}
}This Python function aggregates digit differences analytically without computing each pair individually, scaling efficiently with the number of digits.
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 position-specific digit counters.
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$.
function sumDigitDifferences(nums: number[]): number {
const n = nums.length;
const m = Math.floor(Math.log10(nums[0])) + 1;
let ans: bigint = BigInt(0);
for (let k = 0; k < m; ++k) {
const cnt: number[] = Array(10).fill(0);
for (let i = 0; i < n; ++i) {
++cnt[nums[i] % 10];
nums[i] = Math.floor(nums[i] / 10);
}
for (let i = 0; i < 10; ++i) {
ans += BigInt(cnt[i]) * BigInt(n - cnt[i]);
}
}
ans /= BigInt(2);
return Number(ans);
}func sumDigitDifferences(nums []int) (ans int64) {
n := len(nums)
m := int(math.Floor(math.Log10(float64(nums[0])))) + 1
for k := 0; k < m; k++ {
cnt := [10]int{}
for i, x := range nums {
cnt[x%10]++
nums[i] /= 10
}
for _, v := range cnt {
ans += int64(v) * int64(n-v)
}
}
ans /= 2
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2 * d), where n is the number of elements and d is the total number of digits. Space Complexity: O(1) since strings are handled internally. |
| 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 position-specific digit counters. |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n^2 * d) | O(1) | Good for understanding the problem or when n is very small |
| Digit Position Counting | O(n * d) | O(d * 10) | Optimal solution for large arrays; replaces pair comparisons with digit frequency counting |
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.