Sum of Digit Differences of All Pairs - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [13, 23, 12]

› Output: 4

💡 Note: Pair (13,23): digits differ at position 1 (3≠2) → +1. Pair (13,12): digits differ at position 1 (3≠2) → +1. Pair (23,12): digits differ at position 0 (2≠1) and position 1 (3≠2) → +2. Total: 1+1+2=4

Example 2 — All Same Digits

$ Input: nums = [10, 10, 10]

› Output: 0

💡 Note: All numbers are identical, so no digit positions differ between any pairs. Total differences = 0

Example 3 — Two Numbers

$ Input: nums = [123, 456]

› Output: 3

💡 Note: Only one pair (123,456): all three digit positions differ (1≠4, 2≠5, 3≠6) → +3. Total: 3

Constraints

2 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] < 10¹⁰
All integers in nums have the same number of digits

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12

The key insight is to count digit frequencies at each position and use mathematical formulas instead of comparing every pair. The optimal approach uses frequency counting to achieve O(n×d) time complexity, where n is array length and d is number of digits. For each position, calculate different pairs as total_pairs - same_digit_pairs. Time: O(n×d), Space: O(d)

Common Approaches

✓ Brute Force

⏱️ Time: O(n² × d) Space: O(1)

For each pair of numbers in the array, compare them digit by digit and count the positions where digits differ. Sum up all differences across all pairs.

Frequency Count Optimization

⏱️ Time: O(n × d) Space: O(d)

For each digit position, count the frequency of each digit (0-9). For each position, the number of different pairs is total_pairs - same_digit_pairs. Use mathematical formula to avoid nested loops.

Brute Force — Algorithm Steps

Iterate through all pairs (i, j) where i < j
For each pair, compare digits at each position
Count positions where digits differ
Add to total sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Pick Pair

Select two numbers to compare

Compare Digits

Count different digits at same positions

Add to Sum

Add difference count to total

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int totalDiff = 0;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            char str1[20], str2[20];
            sprintf(str1, "%d", nums[i]);
            sprintf(str2, "%d", nums[j]);
            
            int len = strlen(str1);
            for (int k = 0; k < len; k++) {
                if (str1[k] != str2[k]) {
                    totalDiff++;
                }
            }
        }
    }
    
    return totalDiff;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for array
    int nums[1000];
    int count = 0;
    char* ptr = line + 1; // Skip '['
    
    while (*ptr && *ptr != ']') {
        nums[count++] = atoi(ptr);
        while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
        if (*ptr == ',') ptr++;
    }
    
    int result = solution(nums, count);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × d)

Nested loops for n² pairs, each comparison takes O(d) where d is number of digits

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

8.5K Views

Medium Frequency

~15 min Avg. Time

235 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Sum of Digit Differences of All Pairs - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler