Sum of Digit Differences of All Pairs

Medium
1006.

Sum of Digit Differences of All Pairs

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.

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 <= 1000
  • 1 <= nums[i] < 10^9
  • All integers in nums have the same number of digits.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var sumDigitDifferences = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Sum of Digit Differences of All Pairs

  1. Hint 1

    The positions are independent — total the differences one digit position at a time.

  2. Hint 2

    At one position, count how many numbers show each digit 0 through 9.

  3. 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

  1. Find the shared digit count from the first number.
  2. For each position, peel the last digit of every number with % 10 and tally the ten digits, then divide each number by 10.
  3. 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) is c * (c - 1) / 2; using c² 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 total

Java

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