Sum of Digit Differences of All Pairs — Problem & Solution
Sum of Digit Differences of All Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Sum of Digit Differences of All Pairs is a medium coding problem on arrays, hash table and math, asked in Amazon, Google and Infosys interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Math, 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 <= 10001 <= nums[i] < 10^9All integers in nums have the same number of digits.
Hints for Sum of Digit Differences of All Pairs
Hint 1
The positions are independent — total the differences one digit position at a time.
Hint 2
At one position, count how many numbers show each digit 0 through 9.
Hint 3
Pairs that agree there are the ones to subtract from the total pair count.
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
% 10and 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)isc * (c - 1) / 2; usingc²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 totalJava
public static int sumDigitDifferences(int[] nums) {
int n = nums.length;
int[] work = nums.clone();
int digits = 0;
for (int v = nums[0]; v > 0; v /= 10) digits++;
if (digits == 0) digits = 1;
long total = 0;
for (int p = 0; p < digits; p++) {
int[] cnt = new int[10];
for (int i = 0; i < n; i++) {
cnt[work[i] % 10]++;
work[i] /= 10;
}
long same = 0;
for (int d = 0; d < 10; d++) same += (long) cnt[d] * (cnt[d] - 1) / 2;
total += (long) n * (n - 1) / 2 - same;
}
return (int) total;
}C++
int sumDigitDifferences(vector<int>& nums) {
int n = (int) nums.size();
vector<int> work = nums;
int digits = 0;
for (int v = nums[0]; v > 0; v /= 10) digits++;
if (digits == 0) digits = 1;
long long total = 0;
for (int p = 0; p < digits; p++) {
int cnt[10] = {0};
for (int i = 0; i < n; i++) {
cnt[work[i] % 10]++;
work[i] /= 10;
}
long long same = 0;
for (int d = 0; d < 10; d++) same += (long long) cnt[d] * (cnt[d] - 1) / 2;
total += (long long) n * (n - 1) / 2 - same;
}
return (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets